http://kldp.org/node/127968

기본적인 알고리즘은 다음과 같겠죠.

n개의 수를 배열 a[i]에 넣었다고 가정하면요

i=0부터 i=n까지 a[i]와 a[i+1]의 최대공약수의 집합을 g(i)라고 하고

i=0부터 i=n-1까지 g(i)의 교집합을 찾으면 됩니다.

그리고 만약 g(i)중 하나라도 g(i)={1}인 경우가 있으면 그냥 무조건 1이 됩니다.

조금 최적화를 하고 싶다면요

g(0)을 일단 구합니다. 그리고 g(0)의 각 원소들 g(0)[k]에 대해서 a[i]의 약수인지 조사하면 됩니다. 약수이면 남아있고, 약수가 아니면 집합에서 빼버리죠. (여기서 i는 i=2부터 i=n까지)

물론 어떤 순간이든 1만 남게 되면 그때는 루프를 종료시켜도 되겠죠. pseudo code를 만들어 본다면

A = gcd(a[0], a[1])
#여기서 A = {A[0], A[1], ... , A[m]} 처럼 되어 있겠죠
 
for i in range(2,n):
   for j in range(m):
      if A.length==1:
         return A
      if a[i]%A[j]==0:
         A.delete(A[j])
return A
by snowall 2011. 10. 29. 13:38