유클리드 호제법

오늘 이 글이 다룰 내용은

유클리드호제법!!!! 입니다

이 글은 유클리드 호제법을 사용해서 3개의 수를 입력받아

최대공약수를 출력하는 프로그램입니다

제가 자바로 키보드입력을 못받아서 c언어로 써봅니다.

각설하고.

유클리드 호재법은 A와 B의 최대공약수는 B와 두수의 나머지와

같다고 하는 놈입니다.

전체적인 프로그램은 

#include<stdio.h>

int Euclid(int one, int two);

int main(void)

{

int temp, in1, in2, in3;

temp = Euclid(in1,in2);

printf("최대공약수는 %d입니다.",Euclid(temp,in3));

return 0;

}

생각보다 간단해 보이죠

과연 그럴까?

이제 핵심인 Euclid함수를 짜 보죠

int Euclid(int one, int two)

{

    int temp;

/*호제법을 쓰려면 A는 B보다 커야합니다.*/

if (one<two){

      temp = one;

one = two;

two = temp;

  }

while (1){

           /*one과 two가 같거나 two가 0이면

             one이 최대공약수입니다.

     */ 

    if (one==two || two==0)

        return one;

 /*앞서했던 과정을 최대공약수가 나올때까지

    반복할 준비를 합니다.*/

 temp = one%two; //두 수의 나머지를 구합니다.

     one = two;

       two = temp;

}

}

파이썬으로는 캐스트연산자의 사용법을

까먹어서 혼이 났었습니다.

ps.프로그래밍의 핵심은 언어가 아닌 알고리즘입니다!