열혈강의 C프로그래밍 – 도전! 프로그래밍 ONE – 3

두 개의 정수를 입력받아서 최대 공약수(GCM)를 구하는 프로그램을 작성해 보자.

#include <stdio.h>

int gcm(int a, int b);

int main(void)
{
int val1, val2;

printf(”두 개의 정수 입력 : ”);
scanf(”%d %d”, &val1, &val2);

printf(”G C M : %d\n”, gcm(val1, val2));

return 0;
}

int gcm(int a, int b)
{
int g;

for(g=(a<b)? a:b; ; g–)
if(a%g==0 && b%g==0)
return g;
}

유클리드 호제법을 이용해서 문제를 풀어보자.

#include <stdio.h>

int gcm(int a, int b);

int main(void)
{
int val1, val2;

printf(”두 개의 정수 입력 : ”);
scanf(”%d %d”, &val1, &val2);

printf(”G C M : %d\n”, gcm(val1, val2));

return 0;
}

int gcm(int a, int b)
{
int r=1;

do
{
r=a%b;
a=b;
b=r;
}while(r!=0);

return a;
}