C언어 공약수, 최대공약수 출력

문제 두 자연수 m,n을 입력받아서 그들의 공약수와 최대공약수를 출력하는 프로그램을 작성하여라.(유클리드 호제법 쓰지 말 것)

요구분석

두 자연수를 입력받음

각각의 공약수를 출력

최대공약수를 출력

해결방법

1.입력받은 각각의 공약수를 출력하고, 두 공약수가 일치하면 배열에 저장하고 최대공약수를 구하여 출력, 두 공약수가 1만 존재할 경우는 서로소 출력

 

배경지식

공약수 구하는 방법 (n%1,2,3,4 ...차례대로 대입)

유클리드 호제법( 주어진 두 개의 정수 a, b 에 대하여, a, b 의 최대공약수를 찾는 방법

정리 : a, b 의 최대공약수가 d 이고, a=bq+r 이라고 하면,

b, r 의 최대공약수도 d 이다.)

 

 

소스코드

#include <stdio.h>

#include <stdlib.h>

void main()

{

int n, m, h, i, j=0, k=0, max=0;

int *na,*ma;

printf("두 자연수를 입력하시오 : ");

scanf("%d %d",&n,&m);

na = (int*)malloc(sizeof(int)*n);

ma = (int*)malloc(sizeof(int)*m);

for(i=1 ; i<n+1 ; i++){

if( !(n%i) )

na[j++] = i;

}

for(i=1 ; i<m+1 ; i++){

if( !(m%i) )

ma[k++] = i;

}

printf("%d의 약수 : ", n);

for(i=0 ; i<j ; i++){

printf("%d ", na[i]);

}

printf("\n%d의 약수 : ", m);

for(i=0 ; i<k ; i++){

printf("%d ", ma[i]);

}

printf("\n");

printf("공약수: ");

for(i=j-1 ; i>=0 ; i--){

for(h=k-1 ; h>=0 ; h--){

if(na[i] == ma[h]){

printf("%d ", na[i]);

if(na[i] > max)

max = na[i];

}

}

}

free(na);

free(ma);

if(max==1)

printf("서로소\n");

else

printf("최대공약수 : %d\n", max);

}

실행결과