Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 37 Ā· Projects and Practice

Project: A Prime Explorer

Build a prime explorer in Python: sieve primes, measure gaps, count twin primes, compare pi(x) with x/ln x, and draw an Ulam spiral.

In this project you build a small toolkit that lets you look at the primes instead of only proving things about them. Number theory is an experimental science as much as a deductive one: Gauss guessed the prime number theorem by staring at tables, long before it was proved. You will write a fast sieve, then use it to measure prime gaps, twin primes and the density of primes, and finally draw the famous Ulam spiral.

We build the project in stages. Each stage uses the previous one, so run the blocks in order, and feel free to change the limits and see what happens.

Stage 1: a fast sieve

The Sieve of Eratosthenes marks multiples of each prime, starting from its square. Using a bytearray and slice assignment makes it run at C speed in Python.

Python Stage 1: the sieve

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.

Ļ€(x) denotes the number of primes up to x. For two million it is 148933, and our count matches.

Stage 2: prime gaps

The gap after a prime is the distance to the next prime. Gaps are at least 2 (after 2), and they get larger on average, but the pattern is erratic. A maximal gap is a gap bigger than all earlier ones.

Python Stage 2: gaps and records

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.

You will notice that the most common gaps are 6, 12, 2, 4 and 10, with multiples of 6 leading: beyond 3, a prime is always one more or one less than a multiple of 6. The records grow slowly: 14 after 113, 18 after 523, 20 after 887, and so on. Cramér's conjecture says a gap never exceeds roughly ln(p)².

Stage 3: twin primes and prime constellations

Twin primes differ by 2: (3, 5), (11, 13), (17, 19). Whether there are infinitely many is unknown, though in 2013 Yitang Zhang proved that there are infinitely many pairs with a gap below 70 million, a bound since lowered to 246.

The Hardy-Littlewood conjecture predicts the count of twin primes below x as about 1.3203 · x / (ln x)².

Python Stage 3: counting twin primes

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 simple formula undercounts by about 15 to 25 percent at these sizes, and the error shrinks slowly. A better version integrates 1/(ln t)² instead of using x/(ln x)². Notice also that every prime triplet has one of two shapes, (p, p+2, p+6) or (p, p+4, p+6), because one of three consecutive odd numbers is a multiple of 3.

Stage 4: how dense are the primes?

The prime number theorem says Ļ€(x) ~ x / ln x. A better estimate is the logarithmic integral li(x) = āˆ«ā‚‚Ė£ dt/ln t.

Python Stage 4: pi(x) against x / ln x and li(x)

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 table shows that x / ln x is always too low, by about 8% at one million, while li(x) is off by only a couple of hundred. The plot shows π(x) as a smooth-looking curve, even though it is a staircase with a step at every prime.

Stage 5: the Ulam spiral

In 1963 Stanislaw Ulam, bored in a lecture, wrote the integers in a square spiral and circled the primes. They lined up along diagonals. The explanation is that diagonals are values of quadratic polynomials such as 4n² + bn + c, and some quadratics are rich in primes (Euler's n² + n + 41 gives primes for n = 0..39).

Python Stage 5: an Ulam spiral in text

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.

Look for lines of # running along diagonals and rows (try a bigger size). The last line checks Euler's polynomial: n² + n + 41 gives primes for every n < 40, and fails at n = 40, where it equals 41².

Extensions

Try these challenges yourself, using functions from the earlier lessons:

  • Use a segmented sieve to list primes in [10¹², 10¹² + 10⁶] using memory proportional to √n.
  • Check Goldbach's conjecture (every even number above 2 is a sum of two primes) for all even numbers up to 10⁶, and plot the number of representations. The pattern is a "Goldbach comet".
  • Compare Ļ€(x; 4, 1) and Ļ€(x; 4, 3), the counts of primes that are 1 or 3 modulo 4. The second one usually leads: this is Chebyshev's bias.
  • Verify your sieve against sympy.primepi.
flowchart LR
    S["sieve"] --> G["gaps"]
    S --> T["twin primes"]
    S --> D["pi(x) vs x/ln x"]
    S --> U["Ulam spiral"]

The sieve is the shared engine of the explorer.

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. Why does the sieve start crossing out multiples of p at p*p?

    A multiple k*p with k < p has a smaller prime factor and was crossed out earlier.
  2. 2. After the gap of 1 between 2 and 3, why are all gaps even?

    The difference of two odd numbers is even.
  3. 3. What does the prime number theorem say?

    The ratio pi(x) / (x / ln x) tends to 1.
  4. 4. What explains the diagonal lines in the Ulam spiral?

    Numbers along a diagonal are values of a quadratic polynomial in n.

Summary

  • A bytearray sieve finds millions of primes in a fraction of a second.
  • Gaps are always even after 2; multiples of 6 are the most common gaps.
  • Twin prime counts follow the Hardy-Littlewood estimate; Ļ€(x) follows li(x) closely.
  • The Ulam spiral reveals prime-rich quadratic polynomials such as Euler's n² + n + 41.

Next: Project: A Toy RSA Messenger