Education Technology

Euclids Algorithm ACT 2

Activity Overview

This activity is part of the module "Code by Numbers" which can be downloaded as a complete booklet from the STEM section of the website. In this activity students use one of the oldest mathematical algorithms and turn it into a Python program. The algorithm efficiently determines the highest common factor of two numbers. Students see how prime factorisation can also be used. 


This activity covers multiple objectives including improved number sense, pseudo-coding, coding, algorithmic thinking, problem solving and investigations.



  • Factors
  • HCF or GCD
  • Pseudo-code
  • Algorithm


  • if
  • % (Modular Arithmetic)
  • while

About the Lesson

This activity is Part 2of the series Code by Numbers. This activity requires students to turn one of the oldest algorithms into Python code. The algorithm determines the highest common factor of two numbers, students then extend this to the highest common factor to a set of numbers. A PowerPoint slide show is provided to provide a visual understanding of the algorithm.