Scribd
Upload
14 views1 page

Euclid's Algorithm for GCD Calculation

The document outlines Euclid's Algorithm for finding the greatest common divisor (gcd) of two numbers, a and b. It describes the procedure step-by-step, where the algorithm repeatedly calculates the remainder until it reaches zero. The final value of b is returned as the gcd.

Uploaded by

bareerasadaf33
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views1 page

Euclid's Algorithm for GCD Calculation

The document outlines Euclid's Algorithm for finding the greatest common divisor (gcd) of two numbers, a and b. It describes the procedure step-by-step, where the algorithm repeatedly calculates the remainder until it reaches zero. The final value of b is returned as the gcd.

Uploaded by

bareerasadaf33
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithm 1 Euclid’s Algorithm

1: procedure Euclid(a, b) ▷ Find the greatest common divisor of a and b


2: r ← a mod b
3: while r ̸= 0 do ▷ We have the answer if r is 0
4: a←b
5: b←r
6: r ← a mod b
7: end while
8: return b ▷ The gcd is b
9: end procedure

You might also like