#include <stdio.h>
int gcd(int x, int y);
int lcm(int x, int y);
int main()
{
int x = 156;
int y = 156;
int g = gcd(x,y);
int l = lcm(x,y);
printf("GCD (%d, %d) : %d\n", x,y,g);
printf("LCM (%d, %d) : %d\n", x,y,l);
}
int gcd(int x, int y) {
/*;
a = qb + r, 0 <= r < b
a => dividend, q => quotient, b => divisor, r => remainder
*/
if (x == y) {
return x /*or y*/;
}
int dividend = x, divisor = y, remainder = 0, quotient = 0;
do {
remainder = dividend % divisor;
quotient = dividend / divisor;
if(remainder) {
dividend = divisor;
divisor = remainder;
}
}
while(remainder);
return divisor;
}
int lcm(int x, int y) {
/*
lcm(x,y) = (x * y) / gcd(x,y)
*/
return x == y ? x /*or y*/ : (x * y) / gcd(x,y);
}
Saturday, November 14, 2009
Greatest Common Divisor and Least Common Multiple functions in C
Below are two functions (with a sample application) that calculate the Greatest Common Divisor and Least Common Multiple of two numbers; a,b
Greatest Common Divisor and Least Common Multiple functions in C
2009-11-14T15:50:00+01:00
Andreas Grech
C|Mathematics|
Subscribe to:
Post Comments (Atom)