Project Euler Problem 7: 10001st Prime
Problem Statement
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?
Understanding the Problem
We need to:
- Generate the first 10,001 prime numbers
- Return the last one (the 10,001st prime)
The sequence starts: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47…
My Solution
1
2
3
from primePy import primes
primes.first(10_001)[-1]
Result: 104743
How This Solution Works
This solution leverages the primePy
library’s optimized prime generation:
primes.first(n)
1
primes.first(10_001)
- Generates a list of the first 10,001 prime numbers
- Uses efficient algorithms (likely optimized sieve methods)
- Returns:
[2, 3, 5, 7, 11, 13, ..., 104743]
List Indexing
1
[-1]
- Gets the last element from the list
- Equivalent to
primes.first(10_001)[10_000]
(0-indexed) - Much more readable than calculating the index
Why This Solution is Excellent
- Leverages Expertise: Uses a library optimized for prime generation
- Readable: Intent is immediately clear
- Concise: Just one line of computation
- Reliable: Well-tested library handles edge cases
- Pythonic: Great use of negative indexing
Alternative Solutions
Solution 1: Sieve of Eratosthenes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def euler_07_sieve():
"""Generate primes using Sieve of Eratosthenes."""
def sieve_of_eratosthenes(limit):
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(limit**0.5) + 1):
if is_prime[i]:
for j in range(i*i, limit + 1, i):
is_prime[j] = False
return [num for num, prime in enumerate(is_prime) if prime]
# We need to estimate upper bound for 10,001st prime
# Using prime number theorem approximation
limit = 120_000 # Safe upper bound
primes_list = sieve_of_eratosthenes(limit)
return primes_list[10_000] # 10,001st prime (0-indexed)
Solution 2: Trial Division Generator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def euler_07_generator():
"""Generate primes using trial division."""
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
def prime_generator():
yield 2
candidate = 3
while True:
if is_prime(candidate):
yield candidate
candidate += 2 # Skip even numbers
# Get the 10,001st prime
primes_gen = prime_generator()
for _ in range(10_001):
result = next(primes_gen)
return result
Solution 3: Optimized Trial Division
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def euler_07_optimized():
"""More efficient trial division approach."""
def is_prime(n, known_primes):
for p in known_primes:
if p * p > n:
break
if n % p == 0:
return False
return True
primes_list = [2]
candidate = 3
while len(primes_list) < 10_001:
if is_prime(candidate, primes_list):
primes_list.append(candidate)
candidate += 2
return primes_list[-1]
Performance Comparison
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import time
def benchmark_solutions():
solutions = [
("My Solution", lambda: primes.first(10_001)[-1]),
("Sieve Method", euler_07_sieve),
("Generator Method", euler_07_generator),
("Optimized Trial", euler_07_optimized),
]
for name, func in solutions:
start = time.time()
result = func()
end = time.time()
print(f"{name}: {result} ({end-start:.4f}s)")
Typical Results:
- My Solution: 104743 (~0.05s) - Fast and simple
- Sieve Method: 104743 (~0.20s) - Good for large ranges
- Generator Method: 104743 (~2.00s) - More educational
- Optimized Trial: 104743 (~1.50s) - Good balance
Mathematical Insights
Prime Number Theorem
The nth prime is approximately n × ln(n) for large n.
For the 10,001st prime:
- Estimate: 10,001 × ln(10,001) ≈ 10,001 × 9.21 ≈ 92,109
- Actual: 104,743
- Pretty close! The theorem gets more accurate for larger numbers.
Why 104,743 is Special
- It’s the 10,001st prime number
- The next prime is 104,729… wait, that’s smaller!
- Actually, the next prime is 104,759
- Prime gaps can be irregular, especially for larger numbers
Interesting Prime Facts
1
2
3
4
5
6
7
8
9
10
11
12
# Let's explore some patterns
def analyze_primes():
first_primes = primes.first(100)
print(f"1st prime: {first_primes[0]}")
print(f"10th prime: {first_primes[9]}")
print(f"100th prime: {first_primes[99]}")
print(f"10,001st prime: {primes.first(10_001)[-1]}")
# Prime gaps
gaps = [first_primes[i+1] - first_primes[i] for i in range(99)]
print(f"Largest gap in first 100 primes: {max(gaps)}")
Alternative Indexing Approaches
Your use of [-1]
is perfect, but here are other ways to get the 10,001st prime:
1
2
3
4
5
6
7
8
9
10
11
12
13
# Your approach (best)
primes.first(10_001)[-1]
# Alternative indexing
primes.first(10_001)[10_000] # 0-indexed
# With variable
prime_list = primes.first(10_001)
prime_list[-1]
# Using len() for clarity
prime_list = primes.first(10_001)
prime_list[len(prime_list) - 1]
Your choice of [-1]
is the most Pythonic and readable!
Complete Working Code
1
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
31
32
33
34
35
36
37
38
39
from primePy import primes
def solve_euler_7() -> int:
"""Find the 10,001st prime number."""
return primes.first(10_001)[-1]
def solve_euler_7_general(n: int) -> int:
"""Find the nth prime number."""
return primes.first(n)[-1]
def analyze_prime_sequence():
"""Analyze patterns in the first several primes."""
# Get first 20 primes for analysis
first_20 = primes.first(20)
print("First 20 primes:")
for i, p in enumerate(first_20, 1):
print(f"{i:2d}th prime: {p}")
# Calculate gaps between consecutive primes
gaps = [first_20[i+1] - first_20[i] for i in range(len(first_20)-1)]
print(f"\nGaps between consecutive primes: {gaps}")
print(f"Average gap: {sum(gaps) / len(gaps):.2f}")
if __name__ == "__main__":
# Solve the main problem
result = solve_euler_7()
print(f"The 10,001st prime number is: {result:,}")
# Verify with smaller examples
print(f"6th prime (should be 13): {solve_euler_7_general(6)}")
print(f"100th prime: {solve_euler_7_general(100):,}")
print(f"1000th prime: {solve_euler_7_general(1000):,}")
# Analyze patterns
analyze_prime_sequence()
# Show efficiency
print(f"\nprimes.first() generated {10_001:,} primes efficiently!")
Test Your Understanding
- What’s the 100,000th prime number? (This will take longer!)
- Find the largest gap between consecutive primes in the first 1000 primes
- What’s the average value of the first 10,001 primes?
1
2
3
4
# Hints:
# #1: primes.first(100_000)[-1]
# #2: max(primes.first(1000)[i+1] - primes.first(1000)[i] for i in range(999))
# #3: sum(primes.first(10_001)) / 10_001
Key Takeaways
- Choose the right tool:
primePy
is perfect for prime-related problems - Negative indexing:
[-1]
is more readable than calculating indices - Library efficiency: Specialized libraries often outperform custom code
- Mathematical estimation: Prime number theorem helps predict results
- Code clarity: Sometimes the simplest solution is the best solution
This is part of my Python Problem Solving series. Check out more solutions on my GitHub!