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:

  1. Generate the first 10,001 prime numbers
  2. 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

  1. Leverages Expertise: Uses a library optimized for prime generation
  2. Readable: Intent is immediately clear
  3. Concise: Just one line of computation
  4. Reliable: Well-tested library handles edge cases
  5. 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

  1. What’s the 100,000th prime number? (This will take longer!)
  2. Find the largest gap between consecutive primes in the first 1000 primes
  3. 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

  1. Choose the right tool: primePy is perfect for prime-related problems
  2. Negative indexing: [-1] is more readable than calculating indices
  3. Library efficiency: Specialized libraries often outperform custom code
  4. Mathematical estimation: Prime number theorem helps predict results
  5. 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!