유클리드 호제법 첫번째 (Euclidean algorithm)

유클리드 호제법을 이용한 최대공약수 구하기 첫번째 : 뺄샘만을 이용하여 구하기.

일단 증명은 위키페디아 참조...

1. 두개의 수치를 입력

2. i>j 일때는 i=i-j를 계산, i<j 일때는 j=j-i를 계산한다.

3. i=j 일때 루프에서 빠져나온다.

4. i를 최대공약수로 출력한다..

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

// //  main.c //  Euclidean_algorithm // //  Created by robot on 2014/05/21. //  Copyright (c) 2014年 Rocke. All rights reserved. //   #include <stdio.h>   int main(int argc, const char * argv[]) {     int i,j;          printf("Enter two numbers here (a b):");     scanf("%d %d",&i,&j);          while(1){         if(i>j)             i=i-j;         else if(i<j)             j=j-i;         else             break;     }     printf("Greatest common divisor is %d.\n",i); }

Xcode로 출력한 결과는 아래와 같다.