While Anonymous Monk
suggested skipping all numbers containing (0, 2, 4, 5, 6, 8) in the original thread by YuckFoo
, I independently thought of the idea on my own. I did borrow the 2/4 trick to avoid multiples of 3. The problem space reduction is amazing. In the first 1_000_000 numbers, only 4_220 candidates are tested. Out of those, 621*
are eliminated as not being prime on the very first try.
I was going to use the C version of is_prime() from Re^3: a close prime number but as you saw yourself, it isn't needed.
* Numbers ending in 5 (15 for instance) in the +2 portion of the code are included as candidates. It is possible to eliminate them but the work involved is more than allowing is_prime() to abort on the first try.