[파이썬] 백준 2824 최대공약수

뭔 문제인지 모르겠다. 당연히 시간 초과 날 것 같어서 소인수분해 함수를 이용해서 했지만 시간 초과가 났고, 그냥 math.gcd 를 사용하니 풀렸다.

 

import sys
import math
from collections import Counter
 
 
 
 
def sosu(x):
    d = 2
 
    answer = [ ] 
 
    while d <= x:
        if x % d == 0:
            answer.append(d)
            x = x / d
        else:
            d = d + 1
 
    return answer
 
q = 1
w = 1
 
a = int(input())
 
first = list(map(int,sys.stdin.readline().split(" ")))
 
for i in first:
    q*=i
 
b = int(input())
 
second = list(map(int,sys.stdin.readline().split(" ")))
 
for i in second:
    w*=i
 
"""
one = [ ]
two = [ ]
 
for i in range(0,len(first)):
    k = sosu(first[i])
 
    for j in k:
        one.append(j)
 
for i in range(0,len(second)):
    k = sosu(second[i])
 
    for j in k:
        two.append(j)
 
answer = [ ]
 
 
for i in one:
    if i in two:
        answer.append(i)
        two.remove(i)
 
ans = 1
 
 
/for i in answer:
//    ans *= i
"""
ans = math.gcd(q,w)
 
 
if len(str(ans))>9:
    print(str(ans)[-9:])
else:
    print(ans)