loading...
Cover image for 10001st prime - Project Euler Soution

10001st prime - Project Euler Soution

codeperfectplus profile image CodePerfectPlus Updated on ・1 min read

Problem Solving Series(For Interview) (9 Part Series)

1) Multiples of 3 and 5 - Project Euler Solution 2) Two sum - Leet Code Solution 3 ... 7 3) Check for Armstrong Number 4) Largest palindrome product - Project Euler Solution 5) Smallest multiple - Project Euler Solution 6) Sum square difference - Project Euler Solution 7) 10001st prime - Project Euler Soution 8) Sieve of Eratosthenes 9) Bubble Sort Implementation in Python

10001st prime - Project Euler Soution

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

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

Problem Solving Series(For Interview) (9 Part Series)

1) Multiples of 3 and 5 - Project Euler Solution 2) Two sum - Leet Code Solution 3 ... 7 3) Check for Armstrong Number 4) Largest palindrome product - Project Euler Solution 5) Smallest multiple - Project Euler Solution 6) Sum square difference - Project Euler Solution 7) 10001st prime - Project Euler Soution 8) Sieve of Eratosthenes 9) Bubble Sort Implementation in Python

Posted on by:

codeperfectplus profile

CodePerfectPlus

@codeperfectplus

Skilled in Data Science, Machine Learning, Deep Learning, As Well As Web Development Knowledge. React ❤️ to encourage Author.

Discussion

markdown guide
 

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)))
 

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)))
 

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))
 

It can save time and space complexity.

 

That‘s a quite slow algorithm. I suggest to look at sieve of atkin.

 
 

Trying upto 10001 is not a good idea. And if the constraints go up you might even face TLE. Why don't use sieve?