Hey there, Gabriele here!
Prime numbers are the atoms of mathematics—the fundamental building blocks from which all other integers are constructed. But how do we efficiently find them? Today, I’m excited to share another classic from my Math Problems Code Solutions repository: The Sieve of Eratosthenes.
This elegant algorithm, devised over 2,200 years ago by Greek mathematician Eratosthenes, remains one of the most efficient methods for discovering prime numbers. Let’s explore why this ancient technique still outperforms many modern approaches.
The Problem: Finding the Fundamental
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
The first primes:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...
Why they matter:
- Fundamental Theorem of Arithmetic: Every integer > 1 is either prime or can be uniquely factored into primes
- Example: 60 = 2² × 3 × 5
Finding all primes up to a given number is a fundamental computational problem with applications from cryptography to computer science.
The Algorithm: Elegant Elimination
The Sieve of Eratosthenes works through systematic elimination:
Step-by-Step Process
Finding all primes up to 30:
Step 1: List all numbers from 2 to 30
2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Step 2: Mark 2 as prime, eliminate all multiples of 2
2 3 ✗ 5 ✗ 7 ✗ 9 ✗ 11 ✗ 13 ✗ 15
✗ 17 ✗ 19 ✗ 21 ✗ 23 ✗ 25 ✗ 27 ✗ 29 ✗
Step 3: Next unmarked is 3, eliminate multiples of 3
2 3 ✗ 5 ✗ 7 ✗ ✗ ✗ 11 ✗ 13 ✗ ✗
✗ 17 ✗ 19 ✗ ✗ ✗ 23 ✗ 25 ✗ ✗ ✗ 29 ✗
Step 4: Next unmarked is 5, eliminate multiples of 5
2 3 ✗ 5 ✗ 7 ✗ ✗ ✗ 11 ✗ 13 ✗ ✗
✗ 17 ✗ 19 ✗ ✗ ✗ 23 ✗ ✗ ✗ ✗ ✗ 29 ✗
Step 5: Continue until √30 ≈ 5.48
Result: Primes up to 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
Why This Algorithm is Brilliant
Elegant Simplicity
- No division required: Only marking multiples
- No primality testing: Primes emerge naturally
- Systematic: Each composite marked exactly once (in principle)
- Optimal: Cannot do better for finding all primes up to n
Mathematical Insight
Key observation: To find all primes up to n, only check multiples of primes up to √n
Why? If n is composite, it has a factor ≤ √n. So by √n, all composites are already marked!
Consequence: Massive efficiency gain for large n
Implementation: From Concept to Code
Basic Sieve
def sieve_of_eratosthenes(limit):
"""
Find all prime numbers up to limit using Sieve of Eratosthenes.
Time Complexity: O(n log log n) - nearly linear!
Space Complexity: O(n)
Args:
limit: Upper bound (inclusive)
Returns:
List of all primes up to limit
"""
if limit < 2:
return []
# Create boolean array: True = potentially prime
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False # 0 and 1 are not prime
# Sieve process
for i in range(2, int(limit ** 0.5) + 1):
if is_prime[i]: # i is prime
# Mark all multiples of i as composite
for j in range(i * i, limit + 1, i):
is_prime[j] = False
# Collect primes
return [num for num in range(2, limit + 1) if is_prime[num]]
Optimisation: Start marking from i² because smaller multiples already marked by smaller primes!
Prime Checking Function
def is_prime(n):
"""
Check if a specific number is prime.
Time Complexity: O(√n)
Optimisation: Check only 2 and odd numbers up to √n
"""
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
# Check odd divisors up to √n
for i in range(3, int(n ** 0.5) + 1, 2):
if n % i == 0:
return False
return True
Prime Factorisation
def prime_factorisation(n):
"""
Find prime factorisation of n.
Returns list of prime factors with multiplicities.
Example: 60 → [(2, 2), (3, 1), (5, 1)] means 2² × 3 × 5
"""
if n < 2:
return []
factors = []
# Check for 2
count = 0
while n % 2 == 0:
count += 1
n //= 2
if count > 0:
factors.append((2, count))
# Check odd numbers
divisor = 3
while divisor * divisor <= n:
count = 0
while n % divisor == 0:
count += 1
n //= divisor
if count > 0:
factors.append((divisor, count))
divisor += 2
# If n > 1, it's a prime factor
if n > 1:
factors.append((n, 1))
return factors
Algorithm Complexity Analysis
Sieve of Eratosthenes
| Metric | Complexity |
|---|---|
| Time | O(n log log n) |
| Space | O(n) |
| Optimal for | Finding all primes up to n |
Comparison with trial division for each number:
- Trial division for all numbers up to n: O(n^(3/2))
- Sieve: O(n log log n)
For n = 1,000,000:
- Trial division: ~31 billion operations
- Sieve: ~15 million operations
- Speed-up: ~2000×
Optimisations
Segmented Sieve: For very large n, process in chunks
- Reduces memory from O(n) to O(√n)
- Maintains O(n log log n) time
Wheel Factorisation: Skip multiples of small primes
- Eliminates 2/3 of candidates (multiples of 2, 3)
- Further optimisation possible with more wheels
Real-World Applications
Cryptography
RSA Encryption:
- Uses two large prime numbers (hundreds of digits)
- Security relies on difficulty of factoring their product
- Prime generation is critical
Diffie-Hellman Key Exchange:
- Safe primes: primes p where (p-1)/2 is also prime
- Based on discrete logarithm problem in prime fields
Elliptic Curve Cryptography:
- Operations in finite fields defined by prime moduli
- Prime selection affects security and efficiency
Hash Functions
Prime-based hashing:
- Hash table sizes often chosen as primes
- Reduces clustering in hash tables
- Better distribution of hash values
Random Number Generation
Linear Congruential Generators:
- Use prime moduli for better statistical properties
- Maximal period when modulus is prime
Computer Science Theory
Complexity Theory:
- AKS primality test: Polynomial time for prime checking
- Studying prime gaps and distribution
Algorithm Design:
- Sieve techniques applicable to other problems
- Example: Finding all Pythagorean triples
Running the Sieve
Ready to discover primes yourself?
Quick Start
# Clone the repository
git clone https://github.com/GIL794/Math-Problems-Code-Solutions.git
cd Math-Problems-Code-Solutions/Prime\ Number\ Sieve/
# Run the sieve (Python 3.7+, no external dependencies!)
python prime_sieve.py
Expected Output
Prime Number Sieve
============================================================
Prime Numbers up to 100
------------------------------------------------------------
Total count: 25
All primes:
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97
Prime Distribution Analysis
============================================================
Twin Primes (primes differing by 2):
(3, 5) (5, 7) (11, 13) (17, 19) (29, 31)
(41, 43) (59, 61) (71, 73)
Prime Gaps:
Between 89 and 97: gap of 8
Between 7 and 11: gap of 4
Average gap: ~3.96
Prime Factorisation Examples:
------------------------------------------------------------
60 = 2² × 3 × 5
100 = 2² × 5²
210 = 2 × 3 × 5 × 7
Fascinating Prime Patterns
Twin Primes
Pairs of primes differing by 2: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43)…
Twin Prime Conjecture (unproven): Are there infinitely many twin primes?
- Believed to be true
- Largest known: 2,996,863,034,895 × 2^1,290,000 ± 1 (388,342 digits)
Prime Gaps
The difference between consecutive primes:
Gap between 2 and 3: 1 (only occurrence of gap 1)
Gap between 7 and 11: 4
Gap between 89 and 97: 8
Cramér’s Conjecture: Gap between consecutive primes near n is approximately (ln n)²
Prime Number Theorem
The number of primes ≤ n is approximately:
π(n) ≈ n / ln(n)
For n = 1,000,000:
- Actual: 78,498 primes
- Approximation: 72,382
- Error: ~8%
Accuracy improves as n grows!
Mersenne Primes
Primes of form 2^p - 1:
2² - 1 = 3
2³ - 1 = 7
2⁵ - 1 = 31
2⁷ - 1 = 127
Used to generate perfect numbers (see previous post!).
Advanced Topics
Goldbach’s Conjecture
Statement (unproven since 1742): Every even integer > 2 is the sum of two primes
Examples:
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 = 5 + 5
100 = 3 + 97 = 11 + 89 = 17 + 83 = ...
Verified for all even numbers up to 4 × 10^18, but not proven!
Sophie Germain Primes
Prime p where 2p + 1 is also prime:
2: 2 × 2 + 1 = 5 ✓
3: 2 × 3 + 1 = 7 ✓
5: 2 × 5 + 1 = 11 ✓
11: 2 × 11 + 1 = 23 ✓
Important in cryptography and number theory.
Lessons from the Sieve
1. Ancient Wisdom Endures
A 2,200-year-old algorithm remains competitive with modern techniques. Sometimes, elegant simplicity beats complexity.
2. Trade-offs Matter
Sieve uses O(n) space to achieve O(n log log n) time. Space-time trade-offs are fundamental to algorithm design.
3. Optimisation Through Insight
Starting from i² instead of 2i seems minor but dramatically reduces operations. Small optimisations compound.
4. Specialised Beats General
Sieve excels at finding all primes but isn’t optimal for checking individual numbers. Choose algorithms based on use case.
Contributing to the Repository
Interested in extending the prime sieve?
Enhancement Ideas
🚀 Optimisations:
- Implement segmented sieve for large ranges
- Add wheel factorisation (skip multiples of 2, 3, 5)
- Parallel sieve using multiple threads
📊 Analysis Tools:
- Visualise prime distribution
- Analyse prime gaps and patterns
- Find prime constellations (twins, triplets, quadruplets)
🔬 Research Extensions:
- Test Goldbach’s conjecture for ranges
- Identify Sophie Germain primes
- Generate Mersenne prime candidates
Performance Insights
Testing on modern hardware (Intel i7, 16GB RAM):
Prime Finding Performance:
------------------------------------------------------------
Up to 100: < 0.001 seconds (25 primes)
Up to 1,000: < 0.001 seconds (168 primes)
Up to 10,000: ~0.002 seconds (1,229 primes)
Up to 100,000: ~0.015 seconds (9,592 primes)
Up to 1,000,000: ~0.12 seconds (78,498 primes)
Up to 10,000,000: ~1.5 seconds (664,579 primes)
Memory Usage:
------------------------------------------------------------
Up to 1,000,000: ~1 MB boolean array
Up to 10,000,000: ~10 MB
Up to 100,000,000: ~100 MB
Remarkably efficient even for large ranges!
Educational Resources
Books
- “The Music of the Primes” by Marcus du Sautoy
- “Prime Obsession” by John Derbyshire
- “An Introduction to the Theory of Numbers” by Hardy & Wright
Online Resources
- OEIS: A000040 (Prime number sequence)
- Prime Pages: Comprehensive prime database
- MathWorld: Prime number theory
- Project Euler: Computational prime challenges
Academic Papers
- Eratosthenes’s original method (historical)
- Modern optimisations and segmented sieves
- AKS primality test (polynomial time)
Ready to Sieve?
Here’s how to get started:
For Developers
- ⭐ Star the repository on GitHub
- 🔍 Implement segmented sieve for memory efficiency
- 🎯 Add parallel processing for multi-core performance
- 💡 Create visualisations of prime distribution
For Mathematicians
- Explore prime gap patterns
- Test unproven conjectures computationally
- Study prime density in different ranges
- Research prime-generating polynomials
For Educators
- Teach algorithm optimisation using sieve
- Demonstrate time-space trade-offs
- Connect to cryptography applications
- Inspire with unsolved problems
What Patterns Do You See?
I’d love to hear from you:
- What prime patterns fascinate you most?
- Have you implemented sieve optimisations?
- What’s your largest prime discovery?
- Which unsolved prime conjecture interests you?
Drop your thoughts below or reach out directly!
Quick Links
🔗 Repository: Math-Problems-Code-Solutions
📧 Contact: gilangellotto@gmail.com
💼 LinkedIn: Connect with me
🌐 Portfolio: gil794.github.io
Final Thoughts
The Sieve of Eratosthenes exemplifies timeless algorithmic elegance. From ancient Greek mathematics to modern cryptographic systems, from teaching algorithm design to securing internet communications, primes and their discovery remain central to computation.
Whether you’re building secure systems, exploring number theory, or simply appreciating mathematical beauty, the sieve offers a perfect blend of simplicity, efficiency, and profound implications. It reminds us that sometimes the oldest solutions are still the best.
Stay curious, keep computing, and remember: in mathematics, the fundamental building blocks often hold the deepest mysteries!
Fascinated by prime numbers? Explore the other challenges in my repository—perfect numbers, Pythagorean triples, magic squares, and more!
Found this enlightening? Share it with fellow mathematicians and algorithm enthusiasts!
Next in the Series: Discovering Pythagorean triples and more mathematical treasures!
Until next time,
Gabriele I. Langellotto
AI Solution Architect | Computational Problem Solver | Prime Number Enthusiast