[알고리즘] 백준 9417 파이썬 - 최대 GCD

9417번: 최대 GCD

문제

정수 M개가 주어졌을 때, 모든 두 수의 쌍 중에서 가장 큰 최대공약수 찾는 프로그램을 작성하시오.

 

문제풀이

#01
def gcd(a,b):
    while b:
        mod=b
        b=a%b
        a=mod
    return a
    
for _ in range(int(input())):
	#02
    x=list(map(int,input().split()))
    ans=0
    for i in range(len(x)):
        for j in range(len(x)):
        	#03
            if i!=j and i>j:
                ans=max(gcd(x[i],x[j]),ans)
    print(ans)

- #01 : 유클리드 호제법을 통하여 최대공약수를 구하는 함수를 만든다.

- #02 : 입력받은 값을 리스트 형태로 x에 저장한다.

           출력할 ans 값의 기본값은 0으로 설정한다.

           for문으로 브루트포스 기법을 사용하여 gcd에 값을 넣는다.

- #03 : 만약 i와 j의 값이 같지 않고, j가 i 인덱스보다 뒤에 값이라면 gcd를 실행한다.

           함수 리턴값이 현재 ans 값보다 큰 값이라면 그 값을 ans에 저장한다.

           최종적으로 테스트마다 ans를 출력해준다.