top of page

Prime Number Tester

Lesson Overview

​In this lesson, students will be provided with unfinished codes to add key code snippets based on mathematics principles (i.e., the definition of prime number) to finish a prime number tester. The purpose is to enable them to experience CT concepts and practices such as variables, loops, conditionals, algorithmic thinking and automation in the practice of reusing and remixing. 

Prior Knowledge

  • Mathematics: Division, Remainder, Factor

Learning Objectives

  1. To acquire the concept of prime number and understand how to use [repeat until XX] to see if there is a factor of 

  2. To know how to use the operator blocks, e.g., [XX mod XX].

  3. To handle multiple conditional blocks simultaneously according to mathematics relationship.

  4. To understand the relationship between multiple nested conditional blocks [if…then...else…]

Mathematics & CT Outcomes

  1. Mathematics: 

    • concept of “factor”, “mod” and their relationship, i.e., if p mod q = 0, then q is a factor of p.

    • concept of prime number

  2. CT Skills: variable, loops; conditionals; operator, algorithmic thinking; automation

Teaching Resources 

The Desmos Activity used in this Task.

Lesson Details

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. For example, ‘11’ cannot be expressed as a product of 1, 2, …, 9 and 10. Therefore ‘11’ is a prime number. Likewise, a composite number (or a composite) is a natural number greater than 1 that is a product of two smaller natural numbers. (On a side note, the process of factorizing a number using primes is called Prime Factorization.)

Complete the remaining part of the code!

Figure 1-Task 1.png

From: https://scratch.mit.edu/projects/554377882

Students' Work

This activity requires students to complete existing code so that it can be used to test whether an integer is a prime number. In this incomplete code, students first need to understand several classifications of judgements: (1) the outermost if...then...else is used to determine that any integer less than 1 is not a prime; (2) the second level of if...then... is used to determine whether the input integer is 2 or greater than 2. Therefore, what needs to be added to the repeat until XX block is the determination of whether an integer greater than 2 is prime, which involves an understanding of the concept of prime numbers and a way of checking whether an integer has a factor. In particular, note that at the end of the code the reader is told that the result of the determination of a prime number is "This number is a prime", so that in the repeat until XX block it is only necessary to (1) negate the composite number and tell the reader the result, and (2) test the prime number without giving the result.

Figure 2-A1-S1.png
Figure 3-A1-S2.png
About this sample: 

These two works have different conditions for the REPEAT UNTIL block:

  1. The method in work 1 compares the factors of x to determine whether it is a prime or not. If x can find a factor that is not its own and is greater than 1, then it is judged not to be a prime, otherwise it is a prime if only x itself and 1 can be found as a factor.

  2. Work 2 determines whether x is prime by checking whether  is factored between 2 and  x/2, so the conditions "repeat until count > x/2" and "x mod count = 0" need to be set. As long as there is a factor of x between 2 and  x/2 (i.e.,       x mod count = 0), then  is not a prime.

Although these two methods are not the same, they both make use of the definition of prime numbers to set the conditions of the iteration.

Possible Challenges and Misconceptions

Sample 1: Not understanding the stopping condition of repeat until and setting it to “count = x/2”, ignoring the case where the count is an odd number.
Figure 4-A1-M1.png

Many students made the mistake of setting the stop condition to [count = x/2] in repeat until block. This is because if x is an odd number, the iteration cannot be stopped and will keep looping so that the variable “count” keeps adding 1 until the first conditional loop "if x mod count = 0" is met, giving an error judgement. For example, if a prime number such as 3 or 5 is entered, if the reader enters a prime number such as 3 or 5, it is judged not to be a prime number.

Also, entering the number “4” will result in an error of judgement as it meets the condition “count = x/2” and the condition in repeat until block will not iterate. Then it will give the final judgement “This number is a prime” resulting in an error judgement.

Sample 2: Misunderstanding the order of setting conditions in a loop
Figure 5-A1-M2.png

Two typical mistakes occur here: firstly, the conditional setting of repeat until neglects to take account of odd numbers; secondly, there is a misunderstanding of the role and relationship of the if...else... and repeat until blocks, resulting in some blocks being placed in the wrong place and not being able to conduct iteration.

Because repeat until “count = x/2”, if an odd number is input in this work, the else part of the iteration [change count by 1] will be executed directly, followed by the “say” and “stop” blocks, so the iteration will only go once. The error result “This number is a prime” is also given directly.

Acknowledgement 

The author would like to thank Alvin Chan for designing this lesson and appreciate all the anonymous teachers and students who participated in this research.

bottom of page