I implemented this in python to compare this version with the semi naive version I am wrote for projecteuler problems a few years ago.
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.
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.
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.
I haven't checked your code. My point is that this sieve is not fast, or "better" than any previous sieves. The only thing I've found interesting is that I haven't found the method in some other number theory books, like Hardy's, or on the internet, and so on.
That is, I wouldn't be surprised if there are better sieving methods out there.
I understand. I was just checking for my own curiosity. May be there is no literature on this because the 6k method is very widely known and seems to be quite a bit faster.
There may be minor tweaks to your algorithm that can make it significantly faster. I'll let you know if I can think of anything :)
Cool. The thing is I arrived to this method by checking some Permutation Groups for something completely tangential, but again, Number Theory is so vast this probably exists somewhere :)
About speed ups, I'm happy to accept pull requests, even if you want to do it in Python. The Erlang bits are just because I wanted to play with the concepts from "chemical programming"
Interesting, however there is an error in the mathematical part (right before the QED).
Somebody already pointed it out in the Issues, seems nothing that cannot be fixed anyway. Let's see
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.
Here is the code: https://gist.github.com/pavanky/9053387
Here are the results:
>$ python isprime.py
>isprime_6k @ 100 5.08 1.54
>isprime_sv @ 100 10.47 2.09
>isprime_6k @ 1000 11.94 2.23
>isprime_sv @ 1000 30.83 3.91
>isprime_6k @ 10000 33.78 3.3
>isprime_sv @ 10000 96.45 7.06
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.
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.