【코딩】 C 언어로 최대공약수와 최소공배수

C 언어로 최대공약수와 최소공배수

 

추천글 : 【C 언어】 C 언어 목차

---

 

#include <stdio.h>
#include <stdlib.h>
/* This source is for finding a greatest common devider and a least common muliflier of 2 numbers */

int main(int argc, char *argv[]) {
    int N1, N2;
    scanf("%d %d", &N1, &N2);
    int Divider = 2;
    int GCD = 1; 
    int LCM = N1 * N2;
	
    while(1){ // The application of Eratosthenes' sieve
		if(Divider > N1 || Divider > N2) break;
		if(N1%Divider == 0 && N2%Divider == 0){
			GCD = GCD * Divider;
			N1 = N1 / Divider;
			N2 = N2 / Divider;
			Divider --; // some primes can devide the given numbers many times.
		}
		Divider ++;
	}
	LCM /= GCD; // if N1 = d*a, N2 = d*b, lcm(N1, N2) = d*a*b
	printf("%d %d", GCD, LCM);
	
    return 0;
}

 

입력 : 2016.02.07 20:59