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.

7 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)

Leave a Reply

Note: I am currently writing my thesis so probably wont have time to reply to your comment
Note: XHTML is allowed. Your email address will never be published.

Subscribe to this comment feed via RSS