10001st prime - Project Euler Soution

#challenge #python #computerscience #algorithms

Topic: 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 10 001st prime number?

You can find the original question here -> Project Euler

Check for Armstrong Number

Deepak Raj ・ Jul 31 '20

#challenge #computerscience #python #algorithms

10001st prime - Project Euler Solution in Python

import itertools

def is_prime(n):
    for i in range(2, n//2 + 1):
        if n % i == 0:
            return False
        else:
            continue
    return True

p = 0
for x in itertools.count(1):
    if is_prime(x):
        if p == 10001:
            print(x)
            break
        p += 1

Share Your Solutions for 10001st prime

Checkout the optimized solution in the comment section.

Top comments (7)

Paddy3118 • Aug 2 '20

Using the Python extensible prime generator: "Iterative sieve on unbounded count from 2" function prime_sieve as posted on Rosetta Code.

from itertools import count, islice
 
def prime_sieve():
    sieved = count(2)
    prime = next(sieved)
    yield prime
    primes = [prime]
    for x in sieved:
        if any(x % prime == 0 for prime in primes):
            continue
        yield x
        primes.append(x)
 
if __name__ == '__main__':
    print("Show the 10,001st prime.\n   =",
        next(islice(prime_sieve(), 10_000, 10_001)))

Paddy3118 • Aug 2 '20

Modified to test less primes:

from itertools import count, islice, takewhile
 
def prime_sieve2():
    sieved = count(2)
    prime = next(sieved)
    yield prime
    primes = [prime]
    for x in sieved:
        possible_prime_divs = takewhile(lambda p: p <= x**0.5, primes)
        if any(x % prime == 0 for prime in possible_prime_divs):
            continue
        yield x
        primes.append(x)

if __name__ == '__main__':
    print("Show the 10,001st prime.\n   =",
        next(islice(prime_sieve2(), 10_000, 10_001)))

Jing Xue • Aug 2 '20

Reuse the smaller primes we found and only try divisions by them instead of every number. Also technically we only need to try up to sqrt(n) which is usually less than n//2 + 1.

import math

def nth_prime(n: int) -> int:
    primes = [2]
    m = 3
    while len(primes) < n:
        j = 0
        sqrt_m = math.sqrt(m)
        is_prime = True
        while primes[j] <= sqrt_m:
            if m % primes[j] == 0:
                is_prime = False
                break
            j += 1
        if is_prime:
            primes.append(m)
        m += 1
    return primes[-1]

print(nth_prime(10001))