5618.공약수

문제

자연수 n개가 주어진다. 이 자연수의 공약수를 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 2 또는 3이다. 둘째 줄에는 공약수를 구해야 하는 자연수 n개가 주어진다. 모든 자연수는 108 이하이다.

출력

입력으로 주어진 n개 수의 공약수를 한 줄에 하나씩 증가하는 순서대로 출력한다.

처음 작성한 코드_Timeover

import time
s = time.time()
import sys
input = sys.stdin.readline

N = int(input())
list2 = []
list3 = []
if N == 2:
    a, b = map(int,input().split())
    for i in range(a):
        if a%(i+1) == 0:
            list2.append(i+1)
    for i in list2:
        if b%int(i) == 0:
            print(i)
else :
    a, b, c = map(int,input().split())
    for i in range(a):
        if a%(i+1) == 0:
            list2.append(i+1)
    for i in list2:
        if b%int(i) == 0:
            list3.append(i)
    for i in list3:
        if c%int(i) == 0:
            print(i)

print('소요시간 : ', time.time()-s)

소요시간 :  5.865200757980347

별 생각 없이 그저 출력에만 초점을 맞춰서 풀었기에 시간초과되었다.
코드 길이를 줄이기 위해 공약수를 구하는 방법을 다시 한 번 찾아보았다.

개선

입력 받은 수 만큼 전부 나눠보지 않아도 그 절반으로도 공약수를 구할 수 있다.
또한 입력 받은 값의 ^0.5 보다 작은 자연수들로 나눈 값으로도 공약수를 구할 수 있다.
ex) 루트12 보다 작은 자연수 1, 2, 3
12/1 = 12, 12/2 = 6, 12/3 = 4 > 공약수 [1,2,3,4,6,12]

새로운 코드

코드를import time
s = time.time()
import sys
input = sys.stdin.readline

N = int(input())
list=[]
list2=[]
if N ==2:
    a, b= map(int, input().split())
    A = a**0.5
    for i in range(int(A)):
        if a%(i+1) == 0:
            list.append(i+1)
            list.append(int(a/(i+1)))
    list.sort()
    for i in list:
        if b%i == 0:
            print(i)
  

else :
    a, b, c = map(int, input().split())
    A = a**0.5
    for i in range(int(A)):
        if a%(i+1) == 0:
            list.append(i+1)
            list.append(int(a/(i+1)))
    list.sort()
    for i in list:
        if b%i == 0:
            list2.append(i)
    for i in list2:
        if c%i == 0:
            print(i)
print('소요시간 : ', time.time()-s) 입력하세요

소요시간 :  11.0259530544281

소요시간이 더 늘어나서 해결책을 찾아보았다.

python 내장함수인 gcd를 이용

O(n)의 시간 복잡도의 알고리즘은 시간초과, O(√n)의 시간 복잡도를 가진 알고리즘 찾아야 함.

and연산자를 이용해서 조건을 설정한 코드

import time
s = time.time()
import sys
input = sys.stdin.readline

N = int(input())
Nlist = list(map(int,input().split()))
gcd=[]

for i in range(1, int(((min(Nlist)+1)/2)+1)):
    if N ==2:
        if Nlist[0]%i == 0 and Nlist[1]%i == 0:
            print(i)
    else:
        if Nlist[0]%i == 0 and Nlist[1]%i == 0 and Nlist[2]%i ==0:
            print(i)

print('소요시간 : ', time.time()-s)

소요시간 :  3.6154119968414307

유클리드 호제법을 이용

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
최대 공약수를 구하고 최대공약수의 약수를 구해 공약수를 구한다.

내장함수를 사용하지 않은 풀이법?