Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 39 ยท Projects and Practice

Project: A Prime Explorer

Build a prime explorer: sieve primes, find twin primes and gaps, test Goldbach's conjecture, plot how primes thin out and compare with the n/ln(n) estimate.

Primes look simple, but they hide patterns that mathematicians are still studying. In this project you will build a small prime explorer from tools you learned in this chapter: the sieve, prime factorization and factors and divisibility. You will count primes, find twin primes, look at gaps between primes, test a famous unproven claim and plot how the primes thin out.

All results are computed by the program, so you see real data. We will use the sieve from the earlier lesson, which is fast enough for hundreds of thousands of numbers.

Stage 1: a fast sieve and counting

First, the sieve. Then count how many primes lie below 10, 100, 1,000 and so on.

Python Stage 1: sieve and count

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 proportion of numbers that are prime falls as the numbers grow. Up to 100, about a quarter are prime; up to 100,000, fewer than one in ten.

Stage 2: twin primes and gaps

Twin primes are pairs that differ by 2, such as (3, 5), (11, 13) and (41, 43). The gap between consecutive primes is the difference between them. Gaps tell you how crowded the primes are.

Python Stage 2: twin primes and the biggest gaps

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 program prints each time a new record gap appears. Gaps between primes can be as large as you like (the numbers n! + 2, n! + 3, ..., n! + n are all composite), yet small gaps such as 2 keep happening.

Stage 3: Goldbach's conjecture

In 1742, Christian Goldbach wrote that every even number greater than 2 seems to be the sum of two primes: 4 = 2 + 2, 10 = 3 + 7 = 5 + 5. No one has proved it, but computers have checked it for every even number up to enormous sizes. You can test a small range yourself.

Python Stage 3: test Goldbach for even numbers

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.

An empty list of failures means the claim holds up to 20,000. That is evidence, not proof: a proof must work for all numbers.

Stage 4: how the primes thin out

A famous result, the prime number theorem, says the number of primes up to n is about n / ln(n) for large n, where ln is the natural logarithm. Let us compare the real count with this estimate on a plot.

Python Stage 4: count of primes against n / ln(n)

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 two curves have the same shape, and the estimate always sits a bit below the true count at this size. The last line prints both numbers at n = 100,000. Mathematicians have much better estimates, but this simple one captures the main trend.

Extension ideas

  1. Find the first prime above 1,000,000 by testing odd numbers with trial division.
  2. List all primes of the form nยฒ + 1 below 1,000 (for example 2, 5, 17, 37).
  3. A prime is a palindromic prime if its digits read the same backward (such as 131). Count them below 10,000.
  4. Use factorint from SymPy to show that 2ยนโฐ - 1 = 1,023 is composite.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which pair is a twin prime pair?

    Twin primes are both prime and differ by 2: 29 and 31 qualify. 15 is composite, and the others differ by 4 or 6.
  2. 2. What does Goldbach's conjecture claim?

    It says every even number above 2 is a sum of two primes. It has been checked on a huge range but is still unproven.
  3. 3. According to the prime number theorem, about how many primes are there up to 100,000? (ln 100,000 โ‰ˆ 11.5)

    100,000 รท 11.5 โ‰ˆ 8,700, close to the true count of 9,592.
  4. 4. Why is a sieve faster than testing each number separately?

    Crossing out multiples marks many composites at once, with no division per number.

Summary

  • A sieve lists all primes up to a limit quickly.
  • Twin primes differ by 2; gaps between primes get larger on average but small gaps keep appearing.
  • Goldbach's conjecture holds in every case tested but has no proof.
  • The number of primes up to n is roughly n / ln(n).
  • Computed evidence is not the same as a proof, but it guides discovery.

Next: Arithmetic and Number Sense