finding gcd of two integers


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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s