Korean, Edit

Finding the Greatest Common Divisor and the Least Common Multiple in C Language

Higher category : 【C Language】 Index of C Language


a. GitHub 



#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;
}


Input: 2016.02.07 20:59

results matching ""

    No results matching ""