PyPro #8 Highest Common Factor

Highest Common Factor in Python

Highest Common Factor in Python

Python code to compute the Highest Common Factor (HCF) of two positive integers

## Highest common factor is the greatest common divisor of two numbers e.g. 10 for 20 & 30, 5 for 5 & 25, 25 for 50 & 75

## THOUGHT PROCESS: HCF will be less than or equal to the smaller of the two numbers and greater than or equal to 1, since 1 is a factor of every number. So we initialize the HCF variable to the smaller of the two, and loop backwards to one and as soon as we find a number which evenly divides the two numbers, we declare it our hcf.

## INPUT
firstNumber = int(input("Enter the first number: "))
secondNumber = int(input("Enter the second number: "))

## LOGIC
# Starting from the upper limit of the highest common divisor i.e. the minimum of the two numbers, check whether it properly divides the two numbers. If not, decrement the number by 1 and repeat the process. As soon as the while loop finds a number which properly divides the two numbers, the current value of hcf variable is the true value of hcf, and it doesn't execute the loop anymore.
## PSEUDO CODE / ALGORITHM: 
# Initialize hcf to the smaller of firstNumber & secondNumber
# While hcf does not evenly divide firstNumber or hcf does not evenly divide secondNumber do 
#     Decrease the value of hcf by 1 
# Report hcf as the greatest common divisor of firstNumber and secondNumber

hcf = min(firstNumber, secondNumber) 
while firstNumber % hcf != 0 or secondNumber % hcf != 0:
    hcf = hcf - 1

## OUTPUTTING CONCLUSION
print("The greatest common divisor of", firstNumber, "and", secondNumber, "is", hcf)

See also:

• Python 101
• Object Oriented Python
• Design Patterns in Python
• 50+ Handy Standard Library Modules
• 60+ Handy Third Library Modules
• 50+ Tips & Tricks for Python Developers
• 50+ Know-How(s) Every Pythonista Must Know