FINDING PRIMES – with Scratch

(c) 2021 George Gadanidis

1. TASK
Get the task as a PDF: https://learnx.ca/wp-content/uploads/2021/04/primes-scratch-task.pdf

The Scratch code shown below finds the first 10 prime numbers and lists them, as shown on the right.

The code is available at: https://scratch.mit.edu/projects/510950947/editor 

  1. Execute, edit and re-execute, and study the code and its output to understand how it works.
  2. Design, code and test a way of making this code more efficient
  3. Design, code and test a way of finding the first 10 twin primes
  4. Design, code and test a pattern that may always give you a prime number (for example, are all numbers like 11, 111, 1111, 11111 always prime)?
  5. Create a poster presentation of what you did, what you learned, and what else you’d like to know.

2. SCAFFOLDING

This ideas below may be used, as needed, to support students in understanding and completing the above task.

1. CONTEXT

A. curriculum connections

  • Math topics: number properties, prime number properties, algebraic expressions
  • Coding topics (Scratch): lists (arrays), conditional structures, search algorithms, code efficiency

B. ABOUT PRIME NUMBERS

Listed below are some of the math and coding topics addressed by this task:

Some questions to research to better understand prime numbers:

  1. What is the definition of a prime number?
  2. What is a composite number?
  3. Why is 1 not a prime number?
  4. How many prime numbers are there?
  5. What are twin primes?
  6. What is the history of prime numbers?
  7. What is the sieve of Eratosthenes?
  8. What is the application of prime numbers today?

2.  LISTS IN SCRATCH

In the sample code shared above, lists are used to store the prime numbers found.

A.  Define a list

To define a list, click on

and then on 

A list is a “variable” but with the ability to store more than one value

Give the list a name that represents its purpose.

The list will appear on the Stage. You can move it and resize it as needed.

If you click to uncheck the list name then it will not be visible on the  Stage.

You may also show/hide a list in code.

B.  Delete from or add to a list

You may delete all items stored in a list.

You typically clear, or delete all items in a list, at the start of your code. 

You may also delete individual items, by specifying their location in the list. 

You may add an item to the list (at the end of the list), insert in a specific location in the list, or replace (update) an item in the list.

C.  Length of a list 

You may find the length of your list if needed.

For example, you can use this to stop a loop once you found 10 prime numbers.

D.  Searching a list 

There are a number of ways to search for an item in a list.

3. MODULAR ARITHMETIC

A.  What is modular arithmetic?

If it is 9 am, what time would it be 5 hours later?

If your answer is 2 pm, then you used modular arithmetic.

9 + 5 = 14

When you divide 14 by 12, the remainder is 2.

In Scratch code, this modulo (mod) operation of finding the remainder is written as: 

B.  Using the modulo (mod) operator to find primes

In the code for finding prime numbers, we use this conditional block: 

If the number we are testing is evenly divisible by another number, that is, if the reminder is 0, then the number is not a prime number.


4. UNDERSTANDING THE CODE

One way to understand the code, as noted in the task statement, is to execute, edit and re-execute, and study the code and its output.

An additional way, is to re-write the code using pseudocode.

Pseudocode uses less formal language to describe the algorithm (the procedure) that the code represents, and to understand it.

Below are 2 ways of writing the above code as pseudocode. Notice the use of indentation to identify coding structures.

How else may the pseudocode be written, perhaps to be more concise, or using different language?

Pseudocode is also useful when designing more efficient algorithms for finding prime numbers.

The design of algorithms, often using pseudocode, is an important component of computer science.

NOTE: Flowcharts may also be used. Microsoft Word, for example, has standard flowchart images (shown below), where text can be added.


5.  MORE EFFICIENT METHODS

Below are some ideas for improving the efficiency of the code for finding prime numbers.

A.  dividE by numbers 2 to n/2

The coding solution shared at https://scratch.mit.edu/projects/510950947/editor tests whether a number is prime or not by dividing it by all the numbers that precede it, staring with the number 2.

This very inefficient because there is no point dividing by any numbers that are more than half the number we are testing.

B.  dividE by 2 and odd numbers 3 to n/2

If we first divide by 2, we eliminate all even numbers that follow. So now we can divide only by the odd numbers 3 to n/2.

C.  dividE by primes 2 to n/2

Since we are keeping a list of all the prime numbers, we can improve our method by dividing the numbers by primes 2 to n/2.

D.  dividE by primes 2 to the square root of n

It is enough to only divide by primes 2 to <= sqrt(n). For example, when testing for the numbers 1-100, you don’t need to divide by any number greater than 10. Can you explain why? Build the code to model and test this method.

E.  Sieve of Eratosthenes

Here’s how the sieve of Eratosthenes (3rd century BC) may be implemented to find all the prime numbers up to 100:

  1. Use a repeat to put the numbers 2-100 in a list
  2. Delete any numbers that are divisible by the list number on the list (2)
  3. Delete any numbers that are divisible by the 2nd number on the list (3)
  4. Delete any numbers that are divisible by the 3rd number on the list (5)
  5. Keep doing this as long as your next number is not bigger than 100
  6. The number left in your list will be all the prime numbers from 1 and 100