while루프를 이용하여 두 개의 정수의 최대공약수 구하기

최대공약수 구하는 알고리즘은 기원전에 이미 유클리드가 개ㅋ발ㅋ

1. 두 수 가운데 큰 수를 x, 작은수를 y
2. y=0이면 공약수는 x와 같다.
3. r <- x%y
4. x <- y
5. 단계 2로 되돌아 간다.

 

//while문을 이용하여 최대공약수 구하기
//유클리드의 알고리즘 이용
#include <stdio.h>

int main(void){
    int temp1, temp2;
    int x, y, r;

    printf("첫 번째 정수를 입력하세요 : ");
    scanf("%d", &temp1);
    printf("두 번째 정수를 입력하세요 : ");
    scanf("%d", &temp2);

    if(temp1>=temp2){
        x = temp1;
        y = temp2;
    }
    else{
        x = temp2;
        y = temp1;
    }                    // 두 정수 중 큰 수를 x에, 작은 수를 y에 대입

    while(y != 0){
        r = x % y ;
        x = y ; 
        y = r ;
    }                    // 유클리드의 최대공약수 구하는 알고리즘

    printf("%d와 %d의 최대공약수는 %d입니다.\\n", temp1, temp2, x);

    printf("x= %d , y= %d ", x, y);

    return 0;
}