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.