Prime Numbers and the Sieve of Eratosthenes
Trial division answers one primality query; the Sieve of Eratosthenes preprocesses an entire range. Every composite has a prime factor at most its square root, which explains both stopping rules.
Prime and composite structure
A prime integer is greater than one and has exactly two positive divisors. Zero, one, and negative integers are not prime. If n is composite, n=ab and at least one factor is at most √n; otherwise both factors would exceed √n and their product would exceed n.
Trial division therefore stops when d·d>n. After checking two, testing only odd divisors halves the work. This is O(√n) per query and appropriate when only a few numbers must be tested.
- Primes are greater than one
- A composite has a small factor
- Trial division is O(√n)
Sieving a whole range
Create a boolean array true from 2 through N, with 0 and 1 false. Scan candidate p from 2 while p²≤N. If p remains true, it is prime; mark p²,p²+p,… as composite.
Starting at 2p would be correct but redundant. Every smaller multiple kp with k<p already contains a smaller prime factor and was marked during that factor's turn. The first possibly unmarked multiple is p².
- Initialize 0 and 1 as non-prime
- Process only surviving p
- Start crossing out at p²
Strike composite multiples through 30
n = 30
prime = [True] * (n + 1)
prime[0] = prime[1] = False
p = 2
while p * p <= n:
if prime[p]:
for x in range(p * p, n + 1, p):
prime[x] = False
p += 1
print("Primes:", ", ".join(str(i) for i in range(2, n + 1) if prime[i]))#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;int main(){int n=30;vector<bool>p(n+1,true);p[0]=p[1]=false;for(int x=2;x*x<=n;x++)if(p[x])for(int y=x*x;y<=n;y+=x)p[y]=false;cout<<"Primes: ";bool first=true;for(int i=2;i<=n;i++)if(p[i]){if(!first)cout<<", ";cout<<i;first=false;}}import java.util.*;class Main{public static void main(String[]z){int n=30;boolean[]p=new boolean[n+1];Arrays.fill(p,true);p[0]=p[1]=false;for(int x=2;x*x<=n;x++)if(p[x])for(int y=x*x;y<=n;y+=x)p[y]=false;System.out.print("Primes: " );boolean first=true;for(int i=2;i<=n;i++)if(p[i]){if(!first)System.out.print(", " );System.out.print(i);first=false;}}}N=30Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29Run the example step by step
Why unmarked numbers are prime
Suppose an unmarked x≤N were composite. It has a prime factor p≤√x≤√N. When the sieve processed p, x was a multiple at least p² and would have been marked—a contradiction. Therefore every remaining true position is prime.
Marking work sums roughly N/2+N/3+N/5+… over primes, giving O(N log log N) operations. The boolean table uses O(N) space.
- Every composite is eventually marked
- Survivors are prime by contradiction
- Space is O(N)
Engineering improvements
Store only odd candidates to halve memory and skip even multiples. For intervals too large to hold, a segmented sieve first finds base primes through √R, then marks their multiples inside blocks of [L,R].
Use p≤N/p instead of p·p≤N when multiplication could overflow. In a segmented block, begin at max(p²,ceil(L/p)·p), carefully normalizing the first multiple.
- Odd-only storage saves space
- Segment large ranges
- Avoid p² overflow
Choosing trial division or a sieve
Use trial division for isolated values, a classic sieve for many queries under one moderate maximum, and a segmented sieve for a distant or memory-heavy interval. More advanced primality tests matter when numbers are huge and the full range is impossible to enumerate.
Test N below two, N exactly two, perfect squares, and boundaries where p² approaches the integer limit. The tracer should show why each composite is struck, not merely display the final primes.
- Workload determines the method
- Perfect squares test the stopping rule
- Explain each strike's prime source
From proof to a robust implementation
Allocate N+1 positions so the numeric value is its own index, then guard N below one before assigning positions zero and one. Iterate candidates while p<=N/p to avoid overflow in pp. For each surviving p, mark from pp using a step of p. Collect results only after marking is complete, or answer membership queries directly from the boolean table.
Test N=0, N=1, N=2, a perfect-square boundary such as 49, and a range ending immediately before and after a square. Compare small outputs with trial division, and measure memory before selecting a huge upper bound. In a segmented sieve, ensure the prime itself is not marked when it lies inside the block and clamp the starting multiple to at least p*p. These details preserve the mathematical marking proof in finite arrays.
For repeated primality queries, keep the table and maximum bound together so callers cannot index beyond the preprocessed range. If the bound must grow, rebuild or extend with a proven incremental method rather than assuming old composite markings cover the new interval. Output validation can also confirm that every reported value passes trial division and every omitted value above one has a divisor.
- Guard small N before indexing
- Use division to avoid square overflow
- Square boundaries expose marking errors