Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 39 ยท Factors, Multiples and Primes

Primes and the Sieve of Eratosthenes

Learn what makes a number prime, test numbers by trial division up to the square root, and list all primes with the Sieve of Eratosthenes in code.

A prime number is a whole number greater than 1 whose only factors are 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. A whole number greater than 1 that is not prime is called composite: it has at least one factor besides 1 and itself, like 12 or 49.

Primes are the building blocks of all whole numbers, as you will see in Prime Factorization. Here you learn to recognize them and to find all the primes up to a limit.

Two special numbers

  • 1 is not prime. It has only one factor (itself). Mathematicians exclude it so that every number has a unique prime factorization.
  • 2 is the only even prime. Every other even number is divisible by 2, so it has a third factor.

Testing whether a number is prime

To test n, try dividing it by the primes 2, 3, 5, 7, ... You only need to try divisors up to โˆšn. If n had a factor larger than โˆšn, its partner in the factor pair would be smaller than โˆšn, so you would have found it already.

Example 1. Is 97 prime? โˆš97 is a little under 10, so test 2, 3, 5, 7.

  • 2: 97 is odd.
  • 3: digit sum 16, not divisible.
  • 5: last digit 7.
  • 7: 7 ร— 13 = 91, 7 ร— 14 = 98, so no.

No divisor found, so 97 is prime.

Example 2. Is 91 prime? โˆš91 is a little under 10. Test 7: 7 ร— 13 = 91. So 91 is composite. It looks prime but is not, a favorite trap.

Python Trial division up to the square root

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop ends when d * d passes n, which is exactly the โˆšn rule. The list at the end shows all primes below 50.

The Sieve of Eratosthenes

What if you want all primes up to 100? Testing each number is slow. The ancient Greek scholar Eratosthenes described a smarter method: instead of testing numbers, cross out the composites.

  1. Write the numbers from 2 up to your limit.
  2. Take the first number not crossed out, 2. It is prime. Cross out all its multiples (4, 6, 8, ...).
  3. Take the next number not crossed out, 3. It is prime. Cross out its multiples.
  4. Repeat. You can stop once the next prime squared is bigger than the limit.
  5. Every number left standing is prime.

Why start crossing at p ร— p? Smaller multiples like p ร— 2 were already crossed out when you processed the smaller primes.

flowchart TD
  A["List 2 to N"] --> B["Pick next unmarked number p"]
  B --> C["Mark multiples of p starting at p squared"]
  C --> D{"p squared > N?"}
  D -- "No" --> B
  D -- "Yes" --> E["Unmarked numbers are prime"]

The sieve as a loop: pick, cross out, stop when p squared exceeds N.

Python The Sieve of Eratosthenes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The result is checked against SymPy's isprime. The sieve is much faster than testing every number one by one when the limit is large.

Some facts about primes

  • There are infinitely many primes. Euclid proved this over two thousand years ago.
  • Primes get rarer as numbers grow, but never run out.
  • Twin primes are primes that differ by 2, like 11, 13 and 17, 19.
  • Apart from 2 and 3, every prime is one more or one less than a multiple of 6. (But not every such number is prime: 25 is 24 + 1.)

Primes have practical uses: online security systems rely on the fact that multiplying two large primes is easy, while finding them again from the product is very hard.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which of these is a prime number?

    51 = 3 ร— 17, 57 = 3 ร— 19 and 63 = 7 ร— 9. 59 has no factor except 1 and itself.
  2. 2. Why is 1 not a prime number?

    A prime needs exactly two factors: 1 and itself. The number 1 has just one factor.
  3. 3. You test a number n between 200 and 250 for primality by trial division. What is the largest divisor you ever need to try?

    You only need divisors up to โˆšn. For n below 250, โˆšn is below 16, so primes up to 13 are enough.
  4. 4. In the sieve for limit 100, why can you stop after crossing out the multiples of 7?

    Any composite number up to 100 has a prime factor of at most 10, so after 7 everything left is prime. The next prime, 11, has 11 ร— 11 = 121 > 100.

Summary

  • A prime has exactly two factors: 1 and itself. 1 is not prime, and 2 is the only even prime.
  • To test n, try divisors up to โˆšn.
  • The Sieve of Eratosthenes crosses out multiples of each prime, starting at its square.
  • There are infinitely many primes.

Next: Prime Factorization