Small issue with simple version of generate_primes.py


#1

This is about the first generate_prime example in chapter 5.9 (not on github afaik). The text refers to the candidate array (is_prime[]) and how it looks like after each iteration. The code does something else though. It overrides each True entry for a prime number in the is_prime[] array to False due to the initialization of the second loop.
The second loop should be initialized with
for i in range(p * 2, n + 1, p):

Thomas


#2

Hi @thomad,

I am not very clear about what you mean, could you go to http://epijudge.com/ to find the files you think is problematic and let us know. It is good to use the test framework there to verify.


#3

You have two versions of the generate_primes method in the book (v1 on page 55 and an optimized v2 on page 56). Only the 2nd version seems to be on epijudge.com. The first version has the issue however.

Thomas


#4

Hi @thomad,

Thanks for your reply, and I figure it out, and it turns out is really interesting that it won’t affect the correctness of this algorithm but definitely there is no need to start the prime sieve from p. I have fixed this, and really appreciate for your report.