Python Programming

Euclid’s Algorithm I

Euclid’s Algorithm allows you to find the HCF of two numbers. The steps of the algorithm are given below:

  1. Ask the user for 2 numbers
  2. Test which one is bigger
  3. Make the bigger number m and the smaller number n
  4. Set r to be the remainder when m is divided by n
  5. Set n to m
  6. Set r to n
  7. If r is 0, the HCF is n. Stop
  8. Else go back to step 5

This article will cover steps 1 to 3. The first step is to create a script and name it

To write the code for step 1, enter the code shown below into the script:

# Ask the user for the first number
first_number = int(input("Please enter the first number: "))

# Ask the user for the second number
second_number = int(input("Please enter the second number: "))

To test which of the input numbers is bigger, we will use the greater than symbol. We will ignore other cases. The code to do this is shown below:

# Test if the second number is bigger than the first number
if (second_number > first_number):
    # Swap if the first number is greater than the second number
    temp = second_number
    second_number = first_number
    first_number = temp

# Print out to check the swap
print(first_number, second_number)

Now the program can receive input and swap them correctly. Below is an image of a running program.

Sample Program Run

Leave a Reply

Your email address will not be published. Required fields are marked *