Find the GCD of two numbers?

Answer 1

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

}

Answer 2

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

}

Answer 3

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

Answer 4

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

Answer 5

#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)

Answer 6

There are two methods which are generally used:

• Euclid's method

1. Divide the larger number by the smaller to give a result and remainder.
2. If the remainder is zero (0), the smaller number is the GCD.
3. Replace the larger by the smaller
4. Replace the smaller by the remainder
5. Repeat the process.

During the process the result of each division is not needed, only the remainder is important. Example GCD of 1260 and 4158:

4158 ÷ 1260 = 3 r 378

1260 ÷ 378 = 3 r 126

378 ÷ 126 = 3 r 0

GCD of 1260 and 4158 is 126.

• Method of prime factorisation.

Express each number in its prime factorisation in power form and then multiply together the common primes to their lowest power. Example GCD of 1260 and 4158:

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.

Answer 7

#include<stdio.h>

#include<conio.h>

int

Answer 8

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

Answer 9

int gcd(int x,int y)

{

if(y==0)

return x;

return gcd(y,x%y);

}

Answer 10

Yes.