백준 파이썬 9417번 - 최대GCD

 

9417번: 최대 GCD

정수가 여러개 주어졌을 때 모든 두 수의 쌍 중에서 가장 큰 최대공약수를 찾아야 한다 

포인터 두 개를 이용하여 모든 두 쌍의 GCD를 구하는 방법을 이용했다 

 

길이가 n인 리스트가 존재한다면 

for i in range(n-1):
    for j in range(i+1,n):

이렇게 처음 반복문은 가장 처음부터 마지막 두 번째 숫자까지 (0 to n-1) 

두 번째 반복문은 처음 포인터의 다음 숫자부터 마지막 숫자까지 (i+1 to n)

가능한 모든 두 쌍을 조회하는 것이다.

 

def gcd(a,b):
    if b == 0:
        return a 
    aa = a%b
    return gcd(b,aa)
t = int(input())
for _ in range(t):
	a = sorted(list(map(int,input().split())))
	answer = [1] 
	for i in range(0,len(a)-1):
		for j in range(i,len(a)):
			answer.append(gcd(a[i],a[j]))
	print(max(answer))