answersLogoWhite

0


Best Answer

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

}

User Avatar

Wiki User

12y ago
This answer is:
User Avatar
More answers
User Avatar

Wiki User

13y ago

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

}

This answer is:
User Avatar

User Avatar

Wiki User

15y ago

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

This answer is:
User Avatar

User Avatar

Wiki User

15y ago

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

This answer is:
User Avatar

User Avatar

Wiki User

13y ago

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

This answer is:
User Avatar

User Avatar

Wiki User

13y ago

There are two methods which are generally used:

  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.

This answer is:
User Avatar

User Avatar

Wiki User

12y ago

#include<stdio.h>

#include<conio.h>

int

This answer is:
User Avatar

User Avatar

Wiki User

6y ago

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

This answer is:
User Avatar

User Avatar

Wiki User

14y ago

int gcd(int x,int y)

{

if(y==0)

return x;

return gcd(y,x%y);

}

This answer is:
User Avatar

User Avatar

Wiki User

13y ago

Yes.

This answer is:
User Avatar

Add your answer:

Earn +20 pts
Q: Find the GCD of two numbers?
Write your answer...
Submit
Still have questions?
magnify glass
imp
Continue Learning about Engineering

Define flowchart and draw flowchart for GCD of two numbers?

pictorial representation of a program is called a flowchart


What is pseudo code for GCD of two numbers?

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.


How do you write a C program to find the GCD and LCM of two numbers using a switch statement?

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


How do you write a algorithm that gives the GCD of two given numbers?

algorithm GCD (a, b) is:while (a b) doif a > b then a := a - b else b := b - aend whilereturn a


Write a C program to find GCD of 2 numbers using non-recursion?

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

Related questions

How do you find the GCD of two numbers?

use slide


What is the gcd of 12?

You need at least two numbers to find a GCF.


What is the GCD of 336?

You need at least two numbers to find a GCF.


What is the GCD of 1029?

You need at least two numbers to find something in common.


What is the gcd of 24?

You need at least two numbers to find something in common.


What is 26 GCD?

You need at least two numbers to find something in common.


Find two composite numbers with a GCD of 1?

Any two numbers who are relatively prime will workSo look at 9 and 4. Neither is prime and their GCD is 1.You must need two numbers with NO other factors in common.


What is the GCD of 13?

You need at least two numbers to find something in common between them.


To find gcd o two numbers?

You should ask a question here, shouldn't you?


What is the gcd of any two consecutive even numbers?

The GCD is 2.


How do you find the numbers given the gcd and lcm?

if the gcd and lcm are given and one of the numbers are also given,multiply the gcd and lcm and divide them by the given number


What is the GCD of 60?

The greatest common denominator (GCD) refers to a denominator that is COMMON to two or more numbers. You have only one number in the question! The greatest denominator of any number is itself.