Is it a prime number?

Below is a clunky Scratch program to determine if a number is prime.  Middle school students love prime numbers because they're somewhat mysterious and unpredictable.  When I say 'mysterious and unpredictable,' I'm referring to the numbers, but I suppose I could be referring to the kids, too.

Click on image to make it bigger.

This program introduces students to some cool concepts.  One concept is the modulo.  Instead of referring to a textbook definition of modulo, I usually give students some examples of mods and they tell me what it means:

12 mod 6 is 0

5 mod 4 is 1

8 mod 5 is 3

15 mod 6 is 3

50 mod 11 is 6

18 mod 6 is 0

If they have trouble, saying the word "remainder" usually derails their train of thought and gets them on the right track.  

This program starts with finding (initial number) mod (initial number- 1) .

It then loops while decreasing the divisor by 1 and checking each modulo for a zero.

 Yes, this is inefficient.  When it runs across a modulo of zero (as long as the divisor is not 1), it states that the number is not prime.

Another cool concept that kids are fascinated by is the fact that all of our encryption, all the secret codes that keep our bank accounts safe, depends on the difficulty in factoring REALLY large numbers.  Kids will see when they enter a 7 or 8 digit number that it might take a LONG time for the program to determine if the number is prime (or find one of its factors).  Our encryption relies on numbers with tens of thousands of digits, and even the fastest computers in the world would take years to factor them.

Below, I chose the number 7,465,001.  I had no idea whether it was prime, and it took the program about 90 seconds to find one of its factors:  5,437 

A nice challenge to give the students is to have them create a variable that takes on the value of the other factor and display that variable.