BOJ 2942 퍼거슨과 사과

https://www.acmicpc.net/problem/2942
시간 1초, 메모리 128MB
input :

• R G(1 ≤ R, G ≤ 1,000,000,000)

output :

• 사과를 받게되는 선수의 수 N과 나누어 주는 빨간 사과의 수 X와 초록 사과의 수 Y를 출력

최대 공약수를 구하고.
공약수의 약수를 이용해서 r, g를 나눈 값들을 출력해주어야 한다.
최대 공약수를 gcd를 통해서 구하고, 에라토스테네스의 체 쓰는 것처럼 해서. 로 공약수의 약수를 구하자.

import sys
from math import sqrt

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


r, g = map(int, sys.stdin.readline().split())
factor = gcd(r, g)
factor_list = set()

for i in range(1, int(sqrt(factor) + 1)):
    if factor % i == 0:
        factor_list.add(i)
        factor_list.add(factor // i)

for item in factor_list:
    print(item, r // item, g // item)