### 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:])
```

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

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

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

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.