Best Answer

There are two main methods:

- Euclid's method

- Choose one of the numbers to be the dividend of a division and the other to be the divisor.
- Perform the division
- Ignore the quotient and keep the remainder
- If the remainder is zero, the last divisor is the GCD
- Replace the dividend by the divisor
- Replace the divisor by the last remainder
- Repeat from step 2.

- Prime factorisation

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.

Examples:

GCD of 500 and 240:

- Euclid's method:

240 ÷ 20 = 6 r 0

gcd = 20

- Prime factorisation:

240 = 24 x 3 x 5

gcd = 22 x 5 = 20

Q: What algorithm is used to calculate GCD of two integers?

Write your answer...

Submit

Still have questions?

Continue Learning about Other Math

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.

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.

GCD: 75

GCD: 648

GCD: 4

Related questions

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.

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

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

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

Euclid's Algorithm (http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/lec3.pdf). 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.

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.

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

for two positive integers: public static int gcd(int i1, int i2) { // using Euclid's algorithm int a=i1, b=i2, temp; while (b!=0) { temp=b; b=a%temp; a=temp; } return a; }

Euclid's algorithm is a time-tested method for finding the greatest common divisor (GCD) of two numbers. It's based on the principle that the greatest common divisor of two numbers also divides their difference. This algorithm is efficient and works well for large numbers, making it a practical choice in numerous applications. The algorithm operates in a recursive or iterative manner, continually reducing the problem size until it reaches a base case. Here’s how Euclid's algorithm works: print (gcd (a, b) ) # Output: 3ere >a>b , subtract b from a. Replace a with (a−b). Repeat this process until a and b become equal, at which point, a (or b) is the GCD of the original numbers. A more efficient version of Euclid’s algorithm, known as the Division-based Euclidean Algorithm, operates as follows: Given two numbers a and b, where >a> b, find the remainder of a divided by b, denoted as r. Replace a with b and b with r. Repeat this process until b becomes zero. The non-zero remainder, a, is the GCD of the original numbers. In this example, even though a and b are large numbers, the algorithm quickly computes the GCD. The division-based version of Euclid’s algorithm is more efficient than the subtraction-based version, especially for large numbers, as it reduces the problem size more rapidly. Euclid's algorithm is a fundamental algorithm in number theory, with applications in various fields including cryptography, computer science, and engineering. Its efficiency and simplicity make it a powerful tool for computing the GCD, even for large numbers.

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

#include<stdio.h> int gcd (int a, int b) { if (a==0) return b; if (b==0) return a; return a<b ? gcd (a, b%a) : gcd (b, a%b); } int main (void) { int a, b; printf ("Enter two integers: ") scanf ("%d\n", &a); scanf ("%d\n", &b); printf ("The GCD of %d and %d is %d\n", a, b, gcd (a, b)); return 0; }

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.