C 언어 예제, 유클리드 호제법으로 최대공약수 구하기(포인터 이용)

목표는 이렇게 만드는 것이다.

최대공약수를 구할 임의의 N 개의 수를 설정한 뒤에 최대공약수가 계산되게 만든다.

아래는 코드이다.

#include <stdio.h>

int euclid(int *p,int *q);

int main()

{

int i,j,k,l,m;

int *p, *q;

printf("몇 개의 수에 대한 최대공약수를 구하겠습니까? ");

scanf("%d", &i);

printf("최대공약수를 구할 수들을 입력해주세요 \n");

scanf("%d", &k);

for(j=1;j<i;j++)

{

scanf("%d", &l);

if(k < l)

{

p = &l;

q = &k;

}

else

{

p = &k;

q = &l;

}

if(j>1)

{

m=euclid(&k, &l);

k=m;

}

}

printf("입력하신 수들의 최대공약수는 %d 입니다. \n",m);

return 0;

}

int euclid(int *p, int *q)

{

int a, b, c;

a = *p;

b = *q;

if(a % b == 0)

{

return b;

}

else

{

for(;;)

{

c = b;

b = a % b;

a = c;

if(a % b ==0)

{

break;

}

}

return b;

}

}

기본적인 개념은 두 수의 최대공약수를 구하고, 새로운 수가 입력되면 기존의 최대공약수와 새로 입력된 수의 최대공약수를 구하는 것이다. 

해석하자면

#include <stdio.h>

int euclid(int *p,int *q);

int main()

{

int i,j,k,l,m;

int *p, *q;

printf("몇 개의 수에 대한 최대공약수를 구하겠습니까? ");

scanf("%d", &i);

printf("최대공약수를 구할 수들을 입력해주세요 \n");

scanf("%d", &k);

for(j=1;j<i;j++)

{

scanf("%d", &l);

if(k < l)

{

p = &l;

q = &k;

}

else

{

p = &k;

q = &l;

}

일단, 첫 입력되는 수는 for 문 안에 있지 않다. 이후에 새로운 수가 입력되고 그에 따라 최대공약수를 계산하는 연산을 넣으려다 보니 첫 수는 일단 밖으로 빼게 되었다. 생각해보니 굳이 밖으로 빼지 않아도 처리할 수 있을 듯.

또한 호제법으로 최대공약수를 구할 때는 나머지를 구하는 연산이 되어야 하는데, % 연산은 왼쪽에서 오른쪽으로 연산이 진행되므로 큰 수가 왼쪽에 들어가도록 미리 처리를 해 주었다.

if(j>1)

{

m=euclid(&k, &l);

k=m;

}

}

printf("입력하신 수들의 최대공약수는 %d 입니다. \n",m);

return 0;

}

int euclid(int *p, int *q)

{

int a, b, c;

a = *p;

b = *q;

if(a % b == 0)

{

return b;

}

else

{

for(;;)

{

c = b;

b = a % b;

a = c;

if(a % b ==0)

{

break;

}

}

return b;

}

}

이 부분은 유클리드 호제법을 알고리즘화 시킨 것이다. 자세한 설명은 생략