최대 공약수는 줄여서 GCD라고 쓴다. 두 수 A와 B의 최대 공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다. 최대공약수를 구하는 가장 쉬운방법은 2부터 A, B 중 작은 수까지 모든 정수로 나누어 보는 방법이다. 최대 공약수가 1인 두 수를 우리는 서로소라고 한다. int g = 1; for(int i=2; i