I am looking at the Python solution for generating all primes with the Seive of Eratosthenes, but I am trying to infer two things in the solution:
why the initial variable of size is set to the following:
size = (n - 3) // 2 + 1
why the value of p is being updated by the following:
p = i * 2 + 3
The solution in the repository doesn’t actually match the representative solution in the book which appears to be more clear
Hi @dwoot,
There are two solutions we provided in the book, where one is no optimization (e.g., checking even number still). I think the solution you find in repository (https://github.com/adnanaziz/EPIJudge/blob/master/epi_judge_python_solutions/prime_sieve.py) is actually an optimized one where we discussed the way how we optimized in the book.
About the question you have, size is the total possible prime number we have in this n since we don’t check even number, and p is the actually prime number we are going to test, for example, if i = 0, p = 3, i = 1, p = 5, …
Feel free to use the judge framework to play around with printing the value and you will realize that those match what we write in the book.
@tsunghsienlee thanks for the prompt reply. I actually meant to remove my question after I flipped the page and noticed the explanation and optimized solution. But thank you for your kind response!
While you’re here, are candidates generally able to come to the optimal solution using a sieve or even the trial division solution not having encountered it before?
Hi @dwoot,
I think it is possible to come out with some tricks of the optimized solution by candidate itself. For example, not counting even number, using primes to sieve other primes, etc.
I think different interviewers have their own criteria but I think communication is very important here.