Total new question here - and I know a similar question has been asked before - but I've done a bit of work on this and I'm stuck, so I'd appreciate some help.

The exercise I'm stuck on is this:

Write a function that implements Euclid's method for finding a common factor of two numbers. It works like this:

1. You have two numbers, a and b, where a is larger than b
2. You repeat the following until b become zero
3. a is changed to the value of b
4. b is changed to the remainder when a (before the change) is divided by b (before the change)
5. you then return the last vaule of a

This is what I've come up with:

``````def fac(a,b): #defining the function that uses Euclid's method
while b>0:
a, b = b, a%b # changing the numbers a to b, and b to remainder of a/b
return a

a = input("Please define a number for 'a': ") #getting numbers a and b from user
b = input("Please define a number for 'b': ")
a,b = max(a,b),min(a,b) #making sure a>b
euclid = fac(a,b) #running the function on a and b

print euclid #printing the result``````

But it doesn't work and just prints b. I can't see why. Please help by explaining where the problem lies.

Thanks for your time.

Jim

2
Contributors
4
Replies
5
Views
7 Years
Discussion Span
Last Post by jimmy9pints

Same old, same old = add some print statements to tell you what is going on.

``````def fac(a,b): #defining the function that uses Euclid's method
ctr = 0
while b>0:
ctr += 1
a, b = b, a%b # changing the numbers a to b, and b to remainder of a/b
print "a & b are now", a, b, ctr
return a``````

Same old, same old

- I know this is newbie basics - sorry about that.

Thanks to your help, this is what I've ended up with:

``````def fac(a,b):#defining the function that uses Euclid's method
ctr = 0
while b>0:
ctr += 1
a, b = b, a%b # changing the numbers a to b, and b to remainder of a/b
print ctr , ".) a & b are now", a, "&", b
print "There are ", ctr, " common factors."
return a

a = input("Please define a number for 'a': ") #getting numbers a and b from user
b = input("Please define a number for 'b': ")
a,b = max(a,b),min(a,b) #making sure a>b

fac(a,b) #running the function on a and b``````

Seems to run ok.

I know this is newbie basics - sorry about that

As long as you learned something and are making progress. Please mark the thread "Solved". Also, I would place the statement
a,b = max(a,b),min(a,b) #making sure a>b
under the function so you can send any two values to it and have the function take care of the max/min part. And do you want to test for two numbers that are the same, again the function should do this for you.

Seems to run ok.

Capture the value "a" returned by the function.
ret_a = fac(a,b) #running the function on a and b
print "final 'a' value is", ret_a

Edited by woooee: n/a

Thank you everyone.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.