Prime Numbers: Making a List

We’ve looked at what prime numbers are, and how the concept extends (or doesn’t) to 0, 1, and negative integers. The next question many students have is, how can I make a list of prime numbers (or write a computer program to do so)? We’ll learn about the Sieve of Eratosthenes, and list all the prime numbers up to 1000.

Listing primes up to 100, one by one

We’ll start with this question from 2008:

Checking if a Number from 1-100 is Prime

What is an easy way to determine if a number is prime?  
Example: Write the number 100 as the sum of two prime numbers. 

For me it is difficult to determine whether or not a number is prime.  I can but it takes a while.  I want to know a simpler way than trying to multiply a bunch of numbers together.  Well some are obvious but if I'm going from 1-100 I need an easy way.

The problem itself requires trial and error: You have to look at a list of primes and try to find pairs that add to 100 (perhaps by subtracting each prime from 100 and seeing if the result is on the list). We gave such a list three weeks ago: $$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97$$

When we try 97, we find that \(97+3=100\); similarly, \(89+11=100\), \(83+17=100\), \(71+29=100\), \(59+41=100\), \(53+47=100\). There is no shortcut for this.

But what if you don’t have such a list? That’s where Brooke wants help.

Doctor Rick answered:

Hi, Brooke.

There isn't a really easy way, but you can write your own list of prime numbers less than 100 without much trouble (if you can't look up the list, as in our FAQ).  I'll give you some pointers, because it will turn out to be useful every now and then to know the primes under 100.

What we’ll be doing here is not the most efficient way, but is intended to help Brooke gain an understanding of primes and divisibility tests, not only for making a list but also for checking if an individual number is a prime. (Next week, we’ll look at efficient ways to do the latter.)

Doctor Rick’s suggestion is to check each number individually, using the tests he’ll list; I’ll do it to all the numbers in parallel, to save writing, which will lead up to the fast method we’re heading toward.

We’ll start with all the numbers from 1 to 100:

If a number can't be divided by any prime number less than or equal to the square root of the number, then it is prime.  (If you don't know this, we can discuss it further!)  This is a big help, because it means that we can find all the primes under 100 by checking for divisibility by the primes 2, 3, 5, and 7.  The next prime, 11, is greater than the square root of 100 (namely, 10).

This immediately rules out all numbers ending in an even digit except 2 (because they are divisible by 2), and all numbers ending in 0 or 5 except 5 itself (because they are divisible by 5).  All other primes less than 100 must end in 1, 3, 7, or 9.

We’ll see below (and also next week, a different way) why we can stop at the square root.

Here I’ve crossed out all the even numbers (red) and remaining multiples of 5 (green), and erased 1, which is neither prime nor composite:

These divisibility tests are particularly easy, because our base, 10, is a multiple of both. That also makes this easy to represent in a table with rows of 10!

A number is divisible by 3 if the sum of its digits is divisible by 3. That's easy to check for two-digit numbers.  Among the numbers in the 50s, for example, this eliminates 51, 54, and 57.  We already knew 54 was out, but now our list is down to 53 and 59.  You should know your 7-times table and realize that neither of these numbers is on it, so they are both prime.  If you've learned up through 7 times 12, then you don't need to actually do a division until you get past 84.  That's not bad!

Here I’ve erased what I crossed out before, and crossed off all remaining multiples of 3 (red) and of 7 (green):

These tests are considerably harder than for 2 and 5; the method we’ll see next eliminates that difficulty.

Going through the numbers from 2 through 99 in order, I can construct the list of primes fairly quickly.  You'll find that the more you do this, the more you'll start recognizing primes in this range.  I mess up once in a while, such as thinking that 91 is prime--so I still have to check my list by doing the division by 7.  Most of the work, though, as I said, is pretty quick.

Here is our final result:

This agrees with our list above.

Now let’s make the process more efficient, by avoiding the divisions (or divisibility tests) entirely.

The Sieve of Eratosthenes: a game of elimination

Here’s a question from 2002 about a far more efficient method:

How does the Sieve of Eratosthenes Work?

I'm in the 6th grade and right now we are working on the "sieve of Eratosthenes." I'm wondering why and how it works.

Thanks for all your help - you make math actually kinda fun!
-S

A sieve, in real life, is a device with a screen, or many holes, that can let small particles pass through, while holding back large particles or clumps.

This metaphorical sieve is an idea attributed to the ancient Greek mathematician Eratosthenes. Here, the “large particles” it removes are the composite numbers, which are “clumps of primes”. Prime numbers are like grains of sand, or like atoms, from which molecules are made.

Doctor Ian answered, demonstrating with a small example:

Hi S,

We start out with some set of numbers. Normally, that's 1 to 100, but I don't want to write all those, so I'm going to go from 1 to 30. The idea stays the same, though. 

   1  2  3  4  5  6  7  8  9 10
  11 12 13 14 15 16 17 18 19 20
  21 22 23 24 25 26 27 28 29 30

We start by getting rid of 1, because the definition of 'prime' excludes 1:

      2  3  4  5  6  7  8  9 10
  11 12 13 14 15 16 17 18 19 20
  21 22 23 24 25 26 27 28 29 30

The smallest prime is 2.  But anything that is _divisible_ by 2 can't be prime, right?  So we can keep 2, and cross out all its multiples:

      2  3     5     7     9   
  11    13    15    17    19 
  21    23    25    27    29 

As you can see, that wipes out half the numbers we started with!

Although in typing he chose to erase the multiples, the work is easier if you circle the prime and cross off its multiples as he said, leaving them in place:

In this case, we just cross off every second number – no multiplication or division is needed. The same will be true for larger primes as we proceed.

The next prime is 3.  We're going to keep that, and again, we'll wipe out the multiples of 3 - since if something is divisible by 3, it can't be prime:

      2  3     5     7         
  11    13          17    19 
        23    25          29

Here we cross off every third number (half of which have already been crossed off, because they are even); I crossed in a different direction this time just to make them stand out – you don’t have to distinguish this when you do it:

Again, I just had to “count by threes”, and never had to multiply or divide.

Now, what about 4? When we eliminated multiples of 2, we also eliminated multiples of 4, 6, 8, and every other even number! This is how the sieve works so quickly: every time you eliminate the multiples of a prime number, you never have to check those multiples.

As we proceed, all the multiples of any composite number will already have been crossed off when we come to it, so we just skip it. We only check divisibility by primes, which we discover as we go.

So we can just skip to the next prime number, which is 5. Removing the multiples of 5 leaves us with

      2  3     5     7         
  11    13          17    19 
        23                29

And at this point, we'd need numbers over 30 in the sieve to see any effects, since everything we have left is prime.

The only new number we cross off is 25:

There are no multiples of 7 remaining (we’ll see why below), so we can stop.

But do you see the main idea? It's sort of like a game that you can play with an audience full of people. Ask everyone to stand up. Then tell everyone with an 'a' in his or her last name to sit down. Then  tell everyone with an 'e' in a last name to sit down. (Note that someone named 'Apple' would already be sitting.) Then do the same for  'i', 'o', and 'u'. Who will be left standing? Only people with no vowels in their names! That is, people with names like Ng, or Kyzyl, or Flynn, or Zbrtzk.  

If we order the vowels from most frequent to least frequent (eaoiu), then each vowel will eliminate fewer people - partly because it's used less often, and partly because many people have more than one vowel in their names (in much the same way that 6 gets eliminated as a multiple of 2, so it isn't around to be eliminated as a multiple of 3).  

Does this make sense?

In our sieve, we started with the most frequent multiples, and each subsequent prime has fewer.

Where to start, where to stop – and why

Now let’s look at that square root idea that was mentioned before. Here’s a question from 2012:

The Sieve, and Ceiling, of Eratosthenes

I want to teach my kids about prime numbers with the Eratosthenes Sieve, but I have noticed that some websites say to use the factors, 2, 3, 5, and 7, while others say to use all those numbers AND the number 11.

Why is that so? and won't it make a difference to the answer?

I answered:

Hi, Lin.

Can you give me an example of such a site? How they word it will make a difference.

How far you go down the list of primes depends on how big a sieve you are making. Most likely those that used 11 were finding primes past 100; or else, possibly, they were using 11 to help students discover the point I'm about to make, the upshot of which is that, if you are finding primes through 100, you DON'T need to go as far as 11. That's a good thing to experience.

I have more than once encouraged a student to try something I knew would not work, so they could discover for themselves (and hopefully remember) why it wasn’t necessary.

I chose to use an intermediate-sized example:

Let's do a smaller sieve, up to 50, and see how far we have to go.

        2   3   4   5   6   7   8   9  10
   11  12  13  14  15  16  17  18  19  20
   21  22  23  24  25  26  27  28  29  30
   31  32  33  34  35  36  37  38  39  40
   41  42  43  44  45  46  47  48  49  50
 
We first mark 2 as a prime and strike out all its multiples:

      ( 2)  3   /   5   /   7   /   9  //
   11  //  13  //  15  //  17  //  19  //
   21  //  23  //  25  //  27  //  29  //
   31  //  33  //  35  //  37  //  39  //
   41  //  43  //  45  //  47  //  49  //

Here, rather than erasing numbers, I showed only the crossings, in order to keep the places, which help in finding multiples by counting.

Now, the first remaining number, 3, has been shown to be a prime, because it is not a multiple of any prime before it. So we repeat the process with 3, striking out 9, 15, 21, 27, 33, 39, and 45:

      ( 2)( 3)  /   5   /   7   /   /  //
   11  //  13  //  //  //  17  //  19  //
   //  //  23  //  25  //  //  //  29  //
   31  //  //  //  35  //  37  //  //  //
   41  //  43  //  //  //  47  //  49  //

Now we see that 5 is the next prime, so we strike out all its multiples that remain -- namely, 25 and 35:

      ( 2)( 3)  / ( 5)  /   7   /   /  //
   11  //  13  //  //  //  17  //  19  //
   //  //  23  //  //  //  //  //  29  //
   31  //  //  //  //  //  37  //  //  //
   41  //  43  //  //  //  47  //  49  //

Now the next prime is 7. But when we go to strike out its multiples, we find that there is only one -- namely, 49:

      ( 2)( 3)  / ( 5)  / ( 7)  /   /  //
   11  //  13  //  //  //  17  //  19  //
   //  //  23  //  //  //  //  //  29  //
   31  //  //  //  //  //  37  //  //  //
   41  //  43  //  //  //  47  //  //  //

Here is the key:

We COULD now try the next prime, 11; but we'd have nothing to do! Why is this?

Well, did you notice that in each step, the first number we struck out was the SQUARE of the prime we were working with?

   2^2 =  4
   3^2 =  9
   5^2 = 25
   7^2 = 49

There's a good reason for that: any multiple of, say, 7, less than 7*7 has already been struck out because the other factor is smaller than 7! So when we come to 11, the first number we'd strike out would be 121, and that's not in our table of the first 50. (It isn't even in the table for primes through 100.)

This gives us our first shortcut: Don’t start counting multiples at the prime itself; start at its square.

It also tells us when we can stop:

Therefore, we already know that nothing more will be stricken (ever!), so we can mark all the remaining numbers as prime:

      ( 2)( 3)  / ( 5)  / ( 7)  /   /  //
  (11) // (13) //  //  // (17) // (19) //
   //  // (23) //  //  //  //  // (29) //
  (31) //  //  //  //  // (37) //  //  //
  (41) // (43) //  //  // (47) //  //  //

The lesson here is that the first number you DON'T have to use is the first prime the square of which is GREATER than your maximum number, or that squares beyond the largest number in the sieve. To put that the other way around, you only have to use primes that are LESS than the SQUARE ROOT of the maximum.

You don’t need to have calculated the square root ahead of time; in doing the sieve, you will be squaring each prime to find the first multiple, and when the square is past the end, you stop. That’s our second shortcut.

So one way to present the sieve of Eratosthenes up to 100 is to just tell your kids that they can stop after 7 -- but then they may not know why, and the process may seem arbitrary. For the sake of insight, deliberately include 11 before exploring why you don't need to use it.

Now, suppose you were making a sieve for numbers through 1000. What is the last prime you would have to use? It won't be either 7 or 11.

The square root of 1000 is about 31.6; so you’ll stop before you reach 32. That last prime will be 31, which we’ve seen above; but we don’t need to know that before we start!

Here’s a summary of the method, at its most efficient:

1. Write out all the numbers from 1 through N. Drop 1, which is neither prime nor composite.
2. Circle the first remaining number on the list, which initially is 2. That’s a prime (call it p).
3. Square the prime p, and cross it off. If this is past the end of your list, stop; all the remaining numbers are prime.
4. Starting there, cross off every multiple of p, by repeatedly adding p. These are composite.
5. Return to step 2 and repeat.

Sieving for primes through 1000

So let’s close with that sieve for 1000. Each time I mark a prime (with a new background color), I’ll cross out its remaining multiples using that color:

Everything not crossed off is a prime.

Once I had marked 31 as prime, since its square is 961, only that one multiple had to be crossed out (992 being already eliminated), and all remaining unmarked numbers are prime. (All this was done by conditional formatting in a spreadsheet – I didn’t really do all that work by hand!)

It is entirely accidental (honest!) that this post, for Christmas, is about Making a List, and will be followed by Checking Them (twice). Santa Claus is coming to town!