[백준 13412] 서로소 쌍 파이썬

문제

https://www.acmicpc.net/problem/13412

풀이

# https://www.acmicpc.net/problem/13412

import sys
input = sys.stdin.readline

t = int(input())

def gcd(a, b):
  while b > 0:
    a, b = b, a % b
    return a


def count_disjoint_pair(n):
  cnt = 1
  for i in range(2, int(n ** 0.5) + 1):
    if n % i == 0 and gcd(i,  n // i) == 1:
      cnt += 1
  return cnt


for _ in range(t):
  n = int(input())
  print(count_disjoint_pair(n))

+ 배운점

최대 공약수를 구하기 위해 파이썬 math에 있는 gcd를 이용해도 좋다!

# https://www.acmicpc.net/problem/13412

import sys
import math
input = sys.stdin.readline

t = int(input())

def gcd(a, b):
  res = 1
  for i in range(1, max(a,b) + 1):
    if a % i == 0 and b % i == 0:
      res = i
  return res


def count_disjoint_pair(n):
  cnt = 1
  for i in range(2, int(n ** 0.5) + 1):
    if n % i == 0 and math.gcd(i,  n // i) == 1:
      cnt += 1
  return cnt


for _ in range(t):
  n = int(input())
  print(count_disjoint_pair(n))

결과