Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 37 Ā· Divisibility and Primes

Prime Numbers and the Sieve of Eratosthenes

Define primes and composites, test primality by trial division up to the square root, and generate all primes up to n with the Sieve of Eratosthenes in Python.

A prime is an integer greater than 1 whose only positive divisors are 1 and itself: 2, 3, 5, 7, 11, 13 ... An integer greater than 1 that is not prime is composite, like 12 = 3 Ā· 4. The number 1 is neither, and 2 is the only even prime. Primes are the building blocks of multiplication, and a few lessons from now you will prove that every integer above 1 factors into them in exactly one way.

Here you learn how to recognize primes and how to list all primes up to a limit quickly. Both are simple algorithms, and both show up in nearly every later chapter.

Trial division

To decide whether n is prime, try dividing by candidates. The key observation from the divisibility lesson: if n = aĀ·b with 1 < a ≤ b then a ≤ √n. So if n has any factor at all it has one that is at most √n, and you only need to test up to √n.

Python Primality by trial division

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.

For a number near 10⁹, the loop runs about 16,000 times, which is instant. For a 30-digit number it would run 10¹⁵ times, which is hopeless. Chapter 5 shows faster tests; trial division is the baseline.

The Sieve of Eratosthenes

Testing each number separately wastes effort. The ancient Greek sieve finds all primes up to N at once by crossing out multiples:

  1. Write the numbers 2 to N.
  2. Take the smallest number not crossed out, call it p. It is prime.
  3. Cross out p², p² + p, p² + 2p, ... (the multiples of p, starting at p², since smaller multiples were already crossed out by smaller primes).
  4. Repeat until p² > N.

All numbers never crossed out are prime.

flowchart TD
  A["Mark 2..N as candidate"] --> B["p = next unmarked number"]
  B --> C{"p * p > N?"}
  C -->|No| D["Cross out p*p, p*p+p, ..."]
  D --> B
  C -->|Yes| E["Unmarked numbers are the primes"]

The sieve stops once p² exceeds N.

Python The sieve step by step

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.

There are 78,498 primes below one million, and the largest is 999,983. The sieve does about N log log N operations, almost linear, so a million is instant and a hundred million is feasible with a compact array.

Sieve versus repeated trial division

Compare the two approaches on the same job: all primes below 200,000.

Python Sieve against trial division

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 slice assignment s[p*p::p] = ... clears all multiples in one operation, which is the standard way to write a fast sieve in Python.

Useful variations

  • Smallest prime factor sieve: store, for each number, the smallest prime that divides it. Then you can factor any number up to N in time proportional to its number of prime factors. The factorization lesson uses it.
  • Segmented sieve: to find primes in a range [L, R] with R very large, sieve with primes up to √R only, marking just the window.
  • Counting: the function Ļ€(x) counts primes up to x. For example Ļ€(10) = 4, Ļ€(100) = 25, Ļ€(1000) = 168.
Python Smallest prime factor table

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.

Python's sympy.primerange(a, b) and sympy.primepi(x) give a ready-made list and count, which makes them good checks for your own sieve.

Common mistakes

  • Treating 1 as prime. It would break unique factorization, since 6 = 2Ā·3 = 1Ā·2Ā·3 = 1Ā·1Ā·2Ā·3...
  • Stopping the trial-division loop at n/2 instead of √n: correct but much slower.
  • Starting the inner sieve loop at 2p instead of p²: correct but slower; starting at p² is the standard optimization.
  • Forgetting that 2 is prime and that it is the only even prime.

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. Why is it enough to test divisors up to the square root of n?

    If n = a*b with a <= b then a <= sqrt(n), so a composite number always shows a small factor.
  2. 2. In the sieve, why can crossing out start at p*p?

    A multiple k*p with k < p has a prime factor smaller than p, so an earlier pass removed it.
  3. 3. How many primes are there below 100?

    There are 25 primes up to 100: 2, 3, 5, 7, 11, ..., 97.
  4. 4. Which statement is correct?

    Every other even number is divisible by 2. And 9 = 3 * 3, while 1 is neither prime nor composite.

Summary

  • A prime has exactly two positive divisors; 1 is neither prime nor composite.
  • Trial division up to √n decides primality for moderate n.
  • The Sieve of Eratosthenes lists all primes up to N in about N log log N steps.
  • A smallest-prime-factor table factors many numbers quickly.
  • Start the inner sieve loop at p² and test only odd divisors after 2.

Next: GCD, LCM and the Euclidean Algorithm