Problem 7

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?

Solution 1: Brute forcing

I just stored 10001 primes in the way. I used the primes to check for the next primes.

n = 2
counter = 0
primes = []


while counter < 10001: isPrime = True
for p in primes: if not n%p: isPrime = False break
if isPrime: primes += [n] counter += 1
n += 1

print(primes[-1:][0])

This run: ~15.046829223632812. I feel like I am stupid. May b I am.
The output: 104743.

I assumed jumping over multiples of 2, 3 and 5 would reduce the time significantly. Guess what? It just reduce readablity. Of course, it reduced iteration one third of 1 million iteration, while the iteration is much bigger than 1 million.
Here is my try.

n = 29
counter = 0
primes = [2,3,5,7,11,13,17,19,23,29]


while counter < 10001: for i in [2,6,4,2,4,2,4,6]: n += i isPrime = True
for p in primes: if not n%p: isPrime = False break
if isPrime: primes += [n] counter += 1
print(primes[10000])


This run: ~14.499957799911499. I feel like I am stupid. Sure I am.
The output: 104743.


Solution 2: Improved Time

I checked only half of primes to judge the number as prime. This one saved half of the time and iteration not readablity. Feeling smart.

n = 2
counter = 0
primes = []


while counter < 10001: isPrime = True
for p in primes[:counter//2]: if not n%p: isPrime = False break
if isPrime: primes += [n] counter += 1
n += 1

print(n-1)

This run: ~7.953100919723511. This is me.
The output: 104743.


We can use jumping of multiples of 2, 3 and 5 for better. right?

n = 29
counter = 0
primes = [7,11,13,17,19,23,29]


# no multiples of 2, 3, 5
while counter < 9998:
    for i in [2,6,4,2,4,2,4,6]:
        n += i
        isPrime = True

for p in primes[:counter//5]: if not n%p: isPrime = False break
if isPrime: primes += [n] counter += 1

print(primes[9997])


This run: ~2.5937414169311523. Challange is opportunity.
The output: 104743.


Reducing checking of prime to primes less than or equal to square root of n.

n = 29
counter = 0
primes = [7,11,13,17,19,23,29]


# no multiples of 2, 3, 5 while counter < 9998: for i in [2,6,4,2,4,2,4,6]: n += i isPrime = True sqrt_n = n**0.5
for p in primes:
# This is game changer if p > sqrt_n: break
if not n%p: isPrime = False break
if isPrime: primes += [n] counter += 1

print(primes[9997])

This run: ~0.2968735694885254. Wow. I did not dare to think to get answer such time without using Sieve or Miller algorithm.
The output: 104743.