Skip to content

Python: Highest common factor of two numbers

by mat on December 8th, 2009

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.

9 Comments
  1. Martin permalink

    It’s more efficient to use the modulo (%) operator:

    def gcd(a,b):
    while b: a, b = b, a%b
    return a

  2. Juho Vepsäläinen permalink

    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.

  3. 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

  4. @ 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.

  5. 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 :)

  6. morlockhq permalink

    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.

  7. st0le permalink

    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)

  8. Paul permalink

    I’m new to Python Syntax>
    Can somebody explain how the following syntax works :

    while b: a, b = b, a%b

    Thanks

  9. Ryan permalink

    This may be resurrecting a well dead comment thread but I can’t see any timestamps.

    Paul, here’s what is essentially is:
    while b:
    tmp = b
    b = a % b
    a = tmp

    It’s a way to calculate two numbers after doing both operations on the right of the equal sign using unmodified values.

Leave a Reply

Note: XHTML is allowed. Your email address will never be published.

Subscribe to this comment feed via RSS