Naive Parallel Prime Numbers Sieve in Erlang
github.com
github.com
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.
That is, I wouldn't be surprised if there are better sieving methods out there.
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 :)
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"