Best Answer

There are two main methods:

  1. Choose one of the numbers to be the dividend of a division and the other to be the divisor.
  2. Perform the division
  3. Ignore the quotient and keep the remainder
  4. If the remainder is zero, the last divisor is the GCD
  5. Replace the dividend by the divisor
  6. Replace the divisor by the last remainder
  7. Repeat from step 2.
It doesn't matter which number is the dividend and which is the divisor of the first division, but if the larger is chosen as the divisor, the first run through the steps above will swap the two over so that the larger becomes the dividend and the smaller the divisor - it is better to choose the larger as the dividend in the first place.
  • Prime factorisation
Express the numbers in their prime factorisations in power format.

Multiply the common primes to their lowest power together to get the GCD.

The first is limited to two numbers, but the latter can be used to find the gcd of any number of numbers.


GCD of 500 and 240:

  • Euclid's method:
500 ÷ 240 = 2 r 20

240 ÷ 20 = 6 r 0

gcd = 20

  • Prime factorisation:
500 = 22 x 53

240 = 24 x 3 x 5

gcd = 22 x 5 = 20

User Avatar

Wiki User

โˆ™ 2012-08-10 09:58:42
This answer is:
User Avatar
Study guides
See all Study Guides
Create a Study Guide

Add your answer:

Earn +20 pts
Q: What algorithm is used to calculate GCD of two integers?
Write your answer...
Related questions

What is Euclid's Algorithm?

Euclid's algorithm is a popular algorithm to compute the GCD of two numbers. Algorithm: Gcd(a,b) = Gcd(b, a mod b), where a>=b and Gcd(a,0) = a Say we want to find the GCD of 72 and 105. 105 mod 72 = 33, so GCD(72,105) = GCD(33,72) 72 mod 33 = 6, so GCD(33,72) = GCD(6,33) 33 mod 6 = 3 so GCD(6,33) = GCD(3,6) 6 mod 3 = 0 so GCD(3,6) = GCD(0,3) = 3. So the GCD of 72 and 105 is 3.

What is GCD in C Plus Plus?

A C++ implementation of the Binary GCD (Stern's) algorithm is shown in the Related Link below.

What is the greatest common factor of 275 and 375?

Euclid's Algorithm ( the mod function (or %, as used here) is equal to the remainder of x/y. In this first case, 375 mod 275 = the remainder of 375/275, 375/275 is 1 r100 thus 375%275=100. gcd(375,275) => gcd(275,375%275) = gcd(275,100) =>gcd(100,275%100) = gcd(100,75) => gcd(75,100%75) = gcd(75,25) => gcd(25,75%25) = gcd(25,0) ===> gcd is 25.

Find the greatest common divisor in of 11 plus 7i and 18-i?

Use the division algorithm. If b = pa + r, then gcd(b,a) = gcd(a,r). Then you can apply the division algorithm again with a = qr + r' and gcd(a,r) = gcd(r, r'). Note that each time the square norm of the remainder gets smaller and smaller, so eventually this process will terminate and you can get the answer. Here, it should be 1.

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

How do you write recursive algorithm?

Any algorithm, that refers to itself is recursive. Trivial example: gcd (a, b) := a if b=0 b if a=0 gcd (a mod b, b) if a>=b gcd (b mod a, a) if a<b

What is a Java program that finds the greatest common factor of three integers?

public class GCD { public static int gcd(int a, int b) { return (b == 0 ? a : gcd(b, a % b)); } public static int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); } }

What is pseudo code for LCD of two numbers?

The LCD (least common denominator) is better known more generally as the LCM (least common multiple). The LCM of any two integers, typically denoted LCM (a, b), is the lowest positive integer that is evenly divisible by both integers. That is, LCM (a, b) = c such that c/a = c/b. Division by zero is undefined thus it stands to reason that neither a nor b can be zero. However, many people regard LCM (a, 0) = a to be valid even though it is technically undefined, as is LCM (0, 0). Note that either a or b may be negative but LCM (a, b) must always be positive.The product of a and b is obviously a common multiple of a and b. However, it is not necessarily the lowest common multiple. For instance, 20 is the product of 2 and 10 and is therefore a common multiple of 2 and 10. However, the lowest common multiple of 2 and 10 is 10 because 10/2 = 5 and 10/10 = 1. From this we can surmise that LCM (a, b) can be no greater than the product of a and b and it cannot be any less than the largest of a and b.There are several ways to calculate the LCM of two integers, however one of the simplest is by reduction by the greatest common divisor (GCD). That is, GCD (a, b) = c such that a and b are evenly divisible by c. The GCD and LCM are similar types of problem, however the GCD is much easier to calculate and can be implemented efficiently using Euclid's algorithm.In pseudo-code, we can write the GCD (Euclid) algorithm as follows:algorithm GCD (a, b) is:while (a b) doif a > b then a := a - b else b := b - aend whilereturn aFrom this we can now write the LCM algorithm in terms of the GCD algorithm:algorithm LCM (a, b) is: return a / GCD (a, b) * bNote that a * b / GCD (a, b) produces the same result, however it is more efficient to perform the division before the multiplication. This is because a / GCD (a, b) is guaranteed to be an integer that is less than or equal to a and is therefore guaranteed not to overflow. Multiplying that integer by b may still overflow, however the chances of overflow are reduced compared to that of multiplying a and b prior to the division.

What is the gcd of 5 over 8?

That only applies to integers. The GCF of 5 and 8 is 1.

What is the greatest common factor for 14 and 56?

since 14 = 14 x 1 and 56 = 14 x 4 the answer is 14, since it divides evenly into both and clearly nothing larger will.There is a clever algorithm that can help you work this out in the general case:GCD(14, 56) = GCD(14, 56 - 14) = GCD(14, 42)This step (subtract the smaller from the larger) relies on the fact that any number that divides both 14 and 56 also divides 56 - 14.Repeat this:GCD(14, 42) = GCD(14, 42 - 14) = GCD(14, 28)GCD(14, 28) = GCD(14, 28 - 14) = GCD(14, 14)which is clearly 14.This is called Euclid's Algorithm.

Examples of Euclid's algorithm for finding GCD of large numbers?

Use a character array to save the large number

What is the least common multiple of decimals and fractions in C?

To calculate the least common multiple (lcm) of decimals (integers) and fractions you first need to calculate the greatest common divisor (gcd) of two integers: int gcd (int a, int b) { int c; while (a != 0) { c = a; a = b % a; b = c; } return b; } With this function in place, we can calculate the lcm of two integers: int lcm (int a, int b) { return a / gcd (a, b) * b; } And with this function in place we can calculate the lcm of two fractions (a/b and c/d): int lcm_fraction (int a, int b, int c, int d) { return lcm (a, c) / gcd (b, d); }

What is the assembly language program for GCD of two 16 bit unsigned integers using Intel 8086?

alp for lcm of a no

How do you write a C program to find the GCD and LCM. write the flowchart and algorithm of the above program?

This question is not a question. You are supposed to do your homework yourself.

A program to find the LCM of two numbers?

First, calculate the greatest common divisor (gcd) of both numbers. The following recursive function achieves that: int gcd (int a, int b) { if (!a || !b) return 0; if (a==b) return a; // base case if (a>b) return gcd(a-b, b); return gcd(a, b-a); } Now we can compute the lcm from the gcd: int lcm (int a, int b) { return (a / gcd(a, b)) * b; }

A program to find GCD andLCM of two numbers?

// recursive algorithm to return gcd using Euclid's Algorithm int gcd (int a, int b) { if (a<0) a= -a; if (b<0) b= -b; if (a<b) { int tmp; tmp= a; a= b; b= tmp; } if (b == 0) return a; return gcd (b, a%b); } // LCM using gcd int LCM (int a, int b) { int t; t = a*b; if (t<0) t=-t; return t / gcd (a, b); }

How can you find the LCM in c without using any loop and condition?

The LCM can be calculated without using any loop or condition as follows: int lcm (int a, int b) { return a / gcd (a, b) * b; } The problem is that the typical implementation for the GCD function uses Euclid's algorithm, which requires a conditional loop: int gcd (int a, int b) { while (b!=0) b ^= a ^= b ^= a %= b; return a; } So the question is really how do we calculate the GCD without a conditional loop, not the LCM. The answer is that we cannot. There are certainly alternatives to Euclid's algorithm, but they all involve conditional loops. Although recursion isn't technically a loop, it still requires a conditional expression to terminate the recursion.

What is the greatest common factor of 24 72and 132?

gcd(a,b) = greatest common divisor (or factor, whatever) of a and b. For any set of number, a1, a2, a3, ..., you can use the Euclidean algorithm ( to get the gcd(a1, a2), and then again to get gcd(gcd(a1, a2), a3), etc. Often, though, you can eyeball it. So 24*3 = 72. Therefore, gcd(24, 72)=24. 24 does not divide 132, but 12 does (the next biggest factor of 24), so gcd(24, 72, 132)=12.

How do you calculate gcd and LCM in scientific calculator casio fx-991es?

yeah program it... :)

Flowchart of GCD?


Write a recursive algorithm to find the gcd of two numbers? GCD algorithm....GCD(BIG,SMALL)BIG=SMALL*INTEGER + REMAINDERSMALL=REMAINDER*INTEGER + REM#2REMAINDER=REM#2*INTEGER+REM#3When the remainder is 0, then the answer is what's being multiplied by an integer.ExampleGCD(1071,1029)1071=1029*1 + 421029=42*24 + 2142=21*2+0GCD=21Niraj Sharma

Find the GCD of 4 and 6 using algorithm?

An algorithm isn't necessary in this case. The factors of 4 are 1, 2 and 4 and the factors of 6 are 1, 2, 3 and 6. Just by looking at them we can tell that the common factors are 1 and 2 and that the greatest of these is 2.

Write a c program to find GCD of two given integers by using both recursive n non recursive functions?

i love u darling

Flow chart of LCM of two numbers?

(start) [calculate gcd] [calculate product] [divide] (stop)

What is the GCD of 375 and 225?

GCD: 75