Euclidean Algorithm This algorithm finds Greatest Common Divisor (GCD) by perfor

Question

Euclidean Algorithm

This algorithm finds Greatest Common Divisor (GCD) by performing repeated division starting from the two numbers we want to find the GCD of until we get a remainder of 0.

For example, below are the steps to find the GCD of 60 and 24 using Euclid's algorithm.

Divide the larger number by the smaller one. In this case we divide 60 by 24 to get a quotient of 2 and remainder of 12.

Next, we divide the smaller number (i.e. 24) by the remainder from the last division (i.e. 12). So we divide 24 by 12. We get a quotient of 2 and remainder of 0.

Since we already got a remainder of zero, the last number that we used to divide is the GCD of 24 and 60. In this case 12.
Let's look at the steps, find GCD of 24 and 60.

60 ÷ 24 = 2 with a remainder of 12

24 ÷ 12 = 2 with a remainder of 0

We stop here since already got a remainder of 0. The last number we used to divide is 12, so the GCD of 24 and 60 is 12
Description: The program will take two integer numbers as input from the user in an attempt to find the GCD. You should write a program that will take the appropriate input from the user and find out the GCD accordingly. You may assume the user input numbers are valid. Using Python only.

Explanation / Answer

Here is a simple program to find the gcd of given two numbers.

d1=int(raw_input("Enter a number:"))

d2=int(raw_input("Enter another number"))

rem=d1%d2

while rem!=0 :

    d1=d2

    d2=rem

    rem=d1%d2

print "gcd of given numbers is : %d" %(d2)

In the above program takes input from the command line using raw_input() (takes input as a string). And rest of the program is very simple. I run it in python shell it worked fine.

Hope it will use to you

Thank you@

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.