Python: Highest common factor of two numbers
Finding the highest common factor is useful in mathematics and cryptography.
It would be computationally expensive to calculate all the common factors of two numbers and then compare to find the highest factor in common. Instead (as usual) there is a mathematical theory that can be used to speed up this process, in this case it’s the Euclidean algorithm.
The Euclidean algorithm subtracts the smaller number from the larger number, then using this new number and the smaller number repeats this process until the numbers are equal and hence the subtraction goes to zero. This is the highest common factor.
Example:
Find the highest common factor of 252 and 105
252-105=147
147-105=42
105-42=63
63-42=21
42-21=21
21-21=0
Below is the python code to preform this
def hcf(no1,no2): while no1!=no2: if no1>no2: no1-=no2 elif no2>no1: no2-=no1 return no1
This method is quite quick even and scales well for larger numbers. If you know of a faster method or can see any improvements to make then please let me know.
It’s more efficient to use the modulo (%) operator:
def gcd(a,b):
while b: a, b = b, a%b
return a
You can find gcd in the fractions module (http://docs.python.org/library/fractions.html#fractions.gcd). No need to implement one yourself unless you really want to.
By the way 252-105 equals 147, not 145.
This is perhaps more commonly known as “greatest common divisor”, or gcd.
Euclid’s algorithm can be recursively defined as:
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
In your code, you are basically using subtraction to calculate a % b.
A bit more elegant iterative implementation in Python, using the modulo operator, would be:
def gcd(a, b):
while b:
a, b = b, a % b
return a
@ Martin: I would have thought using subtraction would be quicker as modulo uses division however I tested it, and you are right!
@Juho: I did really want to implement it myself, as it’s good to learn the method and maths behind functions. Plus thanks for spotting my error, thats what I get for doing it by hand!
@Bojan: Thanks, I think Martin beat you to it though.
ah, it took me some time to understand how come the 145 in your example is not a multiply of 21, when both 252 and 105 are.
answer: it should be 147
Now that you have the GCD of two numbers, you can use that for an efficient equation to calculate the Least Common Multiple (LCM) or two numbers.
LCM(a, b) = |a * b|/ GCD(a, b)
Math is nifty.
The Binary GCD Algorithm is faster on a Computer…because a lot of its instructions are bit-shifts. So it is faster than Euclid’s on a Computer.
However, i’m not sure how python does it bit shift (maybe it uses multiply/divide by 2)