I implemented this in python to compare this version with the semi naive version I am wrote for projecteuler problems a few years ago.<p>The semi naive version checks only the numbers of the form 6n + 1 and 6n - 1 because all other numbers (6n + 2, 6n + 3, 6n + 4, 6n) are divided by 2 or 3.<p>Here is the code:
<a href="https://gist.github.com/pavanky/9053387" rel="nofollow">https://gist.github.com/pavanky/9053387</a><p>Here are the results:<p>>$ python isprime.py<p>>isprime_6k @ 100 5.08 1.54<p>>isprime_sv @ 100 10.47 2.09<p>>isprime_6k @ 1000 11.94 2.23<p>>isprime_sv @ 1000 30.83 3.91<p>>isprime_6k @ 10000 33.78 3.3<p>>isprime_sv @ 10000 96.45 7.06<p>sv is the sieve version 6k is the semi naive version I mentioned. The first number is the (average) number of comparisons if the number is prime. The second number is the (average) number of comparisons if the number is not prime.<p>It looks like the sieve version is doing a much larger number of comparisons as the numbers get larger. Please let me know if I have done any mistakes in the coding. I did this fairly quickly and need more eyes to double check.
fwiw somebody has raised an issue with the mathematical underpinning: <a href="https://github.com/videlalvaro/erlang-prime-sieve/issues/2" rel="nofollow">https://github.com/videlalvaro/erlang-prime-sieve/issues/2</a>