#include<stdio.h>
#include<conio.h>
int find_gcd(int,int);
int find_lcm(int,int);
int main(){
int num1,num2,gcd,lcm;
clrscr();
printf("\nEnter two numbers:\n ");
scanf("%d %d",&num1,&num2);
gcd=find_gcd(num1,num2);
printf("\n\nGCD of %d and %d is: %d\n\n",num1,num2,gcd);
if(num1>num2)
lcm = find_lcm(num1,num2);
else
lcm = find_lcm(num2,num1);
printf("\n\nLCM of %d and %d is: %d\n\n",num1,num2,lcm);
return 0;
}
int find_gcd(int n1,int n2){
while(n1!=n2){
if(n1>n2)
return find_gcd(n1-n2,n2);
else
return find_gcd(n1,n2-n1);
}
return x;
}
Chat with our AI personalities
#include<stdio.h>
#include<conio.h>
int GCD (int a,int b)
{
if (a<0) a= -a;
if (b<0) b= -b;
if (a==0 b==1 a==b) return b;
if (a==1 b==0) return a;
if (a>b) return GCD (b, a%b);
else return GCD (a, b%a);
}
void main()
{
int x,y;
clrscr();
printf("nEnter 1st number:");
scanf("%d",&x);
printf("nEnter 2nd number:");
scanf("%d",&y);
printf("\nGCD is:%d", GCD(x,y));
getch();
}
And for three number:
int GCD3 (int x,int y, int z)
{
return GCD(x,GCD(y,z));
}
http://wiki.answers.com/Q/Write_a_recursive_algorithm_to_find_the_gcd_of_two_numbers GCD algorithm....
GCD(BIG,SMALL)
BIG=SMALL*INTEGER + REMAINDER
SMALL=REMAINDER*INTEGER + REM#2
REMAINDER=REM#2*INTEGER+REM#3
When the remainder is 0, then the answer is what's being multiplied by an integer.
Example
GCD(1071,1029)
1071=1029*1 + 42
1029=42*24 + 21
42=21*2+0
GCD=21
Niraj Sharma
function gcd(a, b)
{
while b ≠ 0
{
t := b
b := a mod b
a := t
}
return a
}
function gcd(a, b)
{
if b = 0 return a
else return gcd(b, a mod b)
}
Here is a link to it. http://en.wikipedia.org/wiki/Euclidean_algorithm Dr. Chuck
#include<stdio.h>
#include<conio.h>
void main(void)
{
int x,y,i;
clrscr();
printf("Enter Two Numbers = ");
scanf("%d %d",&x,&y);
for(i=x;i>=1;i--)
{
if(x%i==0 && y%i==0)
{
printf("GCD is %d\n",i);
i=0;
}
}
getch();
}
(Very ineffective solution)
There are two methods which are generally used:
4158 ÷ 1260 = 3 r 378
1260 ÷ 378 = 3 r 126
378 ÷ 126 = 3 r 0
GCD of 1260 and 4158 is 126.
1260 = 22 x 32 x 5 x 7
4158 = 2 x 33 x 7 x 11
GCD of 1260 and 4158 is 2 x 32 x 7 = 126
The prime factorisation method is useful in that it can also be used to find the LCM of the numbers by multiplying together the primes across both the numbers to their highest power, example LCM of 1260 and 4158 is 22 x 33 x 5 x 7 x 11 = 41580.
Example: 30 and 42
Factor them.
2 x 3 x 5 = 30
2 x 3 x 7 = 42
Select the common factors.
2 x 3 = 6, the GCF
pictorial representation of a program is called a flowchart
public class GCD { public static void main(String[] args) { //Example how to use this method System.out.println(GCD(15,50)); } //find the greatest common divisor of two numbers public static int GCD(int a, int b){ if (b == 0) return a; return GCD(b, a % b); } } Hope this help to solve you problem.
The following function will return the GCD or LCM of two arguments (x and y) depending on the value of the fct argument (GCD or LCM). enum FUNC {GCD, LCM}; int gcd_or_lcm(FUNC fct, int x, int y) { int result = 0; switch (fct) { case (GCD): result = gcd (x, y); break; case (LCM): result = lcm (x, y); break; } return result; }
algorithm GCD (a, b) is:while (a b) doif a > b then a := a - b else b := b - aend whilereturn a
One way to find the GCD (Greatest Common Divisor) of two numbers is Euclid's method. The following program demostrates this, without using recursion. The third number printed is the GCD of the first two. The highlighted lines are the core of the algorithm.#include int GcdByEuclid (int a, int b) {if (a < 0 b < 0) return -1;while (a > 0 && b > 0) if (a > b) a -= b; else b -= a;if (a == 0) return b; else return a;}int main (int argc, char *argv[]) {int a, b;if (argc < 3) {fprintf (stderr, "Usage: gcd a b\n");return 1;}a = atoi(argv[1]);b = atoi(argv[2]);printf ("%d %d %d", a, b, GcdByEuclid (a, b));return 0;}