1

I've been working at a snail's pace through the problems in Project Euler, and I have arrived at Problem 7 where it asks to give the 10001st prime number. Currently I'm working in Python 3.

What popped into my head is to generate a Sieve of Eratosthenes and store the values in a list. From there, the rest is history, I print the 10001st prime number and move on.

That is what I tried to do, and failed. I'm not quite sure where I went wrong, and I'd like to know why my code doesn't deliver the correct answer? Evidently, what I have created is not a legitimate Sieve of Eratosthenes, but I'd like to know why it's not functioning as I intended it to. If anyone is to correct me, I would appreciate some clarity as I'm relatively new to coding. I'll try to explain what my thoughts were.

First, I created an empty list and created a for loop as shown below to add numbers to it, which don't have 2, 3, 5 or 7 as factors. I didn't worry about 4, 6, 8 or 9 as these are multiples of either 2 or 3 anyway.

sieveLayer1 = []
import math

for i in range(0,50000):
   if ((i % 2 != 0 and i % 3 != 0) and (i % 5 != 0 and i % 7 != 0)):
       sieveLayer1.append(i)
print(sieveLayer1)

After analysing what was created here, I thought that the only non-prime numbers left in my list would've been square numbers, so I used the sqrt method from the math module to filter them out like so:

for j in sieveLayer1:
    if (math.sqrt(j)).is_integer():
        sieveLayer1.remove(j)

If the square root of any of the values iterated over above is a whole number, this implies that the value isn't prime, so I removed it from the list.

As the numbers 2,3,5,7 were filtered out before, I simply created a new list of what I thought was all the prime numbers I needed:

primeList = [2,3,5,7] + sieveLayer1

From here, I thought print(primeList[10000]) would give me what I wanted, but this failed. It gives me 43943. I'm aware that my final answer should be 104,743. I know it's outside the range of my original for loop, but if my Sieve was correct, it would've indicated that my number wasn't the 10001st, and I would've simply adjusted the range. As I said, I wish to see what's wrong with my code and why I'm so far off the correct number.

liam19
  • 11
  • 1
  • Possible duplicate of [Sieve of Eratosthenes - Finding Primes Python](https://stackoverflow.com/questions/3939660/sieve-of-eratosthenes-finding-primes-python) – Patrick Artner Sep 16 '18 at 14:07
  • Stackoverflow is not about peer reviewing, there are other sites (with own rules) to do that - read about it [codereview: how to get the best value out of code review asking questions](https://codereview.meta.stackexchange.com/questions/2436/how-to-get-the-best-value-out-of-code-review-asking-questions). If you just need a reference implementation to look at, have a look at the dupe. – Patrick Artner Sep 16 '18 at 14:09

0 Answers0