[백준] 5618 공약수

📖 문제

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

💻 내 코드

n=int(input())
mlist=list(map(int, input().split()))
res=[]

for i in range (1,min(mlist)+1):
    if n==2:
        if mlist[0]%i==0 and mlist[1]%i==0:
            res.append(i)
    elif n==3:
        if mlist[0]%i==0 and mlist[1]%i==0 and mlist[2]%i==0:
            res.append(i)
            

for i in res:
    print(i) 

• 시간초과가 나온다
  -pypy3로 하면 시간초과가 나오지 않고 잘 돌아가지만 python으로 했을 때 시간초과가 안뜨는 방법이 궁금해서 찾아봄

💡 다른 코드

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

n=int(sys.stdin.readline())
mlist=list(map(int, sys.stdin.readline().split()))
g=gcd(mlist[0],gcd(mlist[1],mlist[-1]))

for i in range(1, g//2+1):
    if g%i==0:
        print(i)
print(g)

• 최대공약수를 구하는 함수를 만들어 최대공약수를 먼저 구한다
• 최대공약수//2+1까지의 공약수를 구해서 출력해 주고 마지막으로 최대공약수 자기 자신까지 출력

참고

• 최대공약수 구하는 내장함수도 있음

from math import gcd
print(gcd(25, 75))