Find the greatest common divisor (gcd) of two integers

Euclid’s algorithm: // most efficient

gcd (x, y) {

step 1: if y = 0, return x. otherwise goto step 2

step 2: gcd (y, x mod y) // recursive call

}

Example:

gcd (80, 50)

gcd (50, 80 mod 50) = gcd (50, 30)

gcd (30, 50 mod 30) = gcd (30, 20)

gcd (20, 30 mod 20) = gcd (20, 10)

gcd (10, 20 mod 10) = gcd (10, 0)

return 10.

Algorithm:

1. gcd (x, y) {

if ( y == 0 )

return x;

gcd (y, x % y)

}

2. while ( y <> 0 ) { // <> = not equals to

a = x % y

x = y

y = a

}

return x

// Another Algorithm finding gcd (x, y)

step 1: find the prime factors of x

step 2: find the prime factors of y

step 3: multiply the common prime factors of x and y

Example :

gcd (60, 24)

prime factors of 60 = 2 * 2 * 3 * 5

prime factors of 24 = 2 * 2 * 2 * 3

common prime factors = 2, 2, 3

multiply them = 2 * 2 * 3 = 12

### Like this:

Like Loading...

*Related*

## Published by Shahab

Completed B.Sc in CSE, @United International University, Dhaka.
Currently working as Development Engineer, Android and iOS Application.
View all posts by Shahab