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