I believe Primes.jl is not nearly as fast as prime number generators available in other languages, such as PrimeSieve.org (Python version). I would love to learn I’m wrong so I wouldn’t have to worry and could move on in Julia.
Assuming I’m correct, and given that my code spends almost all of its time generating primes AND I run the code for months at a time before getting results… I’m looking for options… and I’m wondering if I might be better off going back to NumPy/Python now that Mojo is in play. Or am I missing some simple understanding about performance or lacking a tool? Any advice?
Probably a silly question but did you profile your code to make sure you do indeed spend most of your time in Primes.jl, and not in another bottleneck that could possibly be lifted?
the prime sieve in primes.jl is far from optional. FastPrimeSieve · Julia Packages is a bunch faster. i want to improve the primes.jl one while keeping it a bit prettier than the massive unrolled loop of fastprimesieve.jl, but haven’t gotten around to it yet.
Out of curiosity, didn’t you say before that you’re fine with just counting the primes, as opposed to generating them?
BTW I moved this to Offtopic.
Yes.
1 Like
Get cracking! 
I’ve always needed to generate primes, but I do it in batches of 10^8 so as to keep the array size down. To track where I am in those batches, I sometimes need to know the count.
Would a generator that produces the primes 1 at a time work for you? The way you’re currently working is really innefficient because you keep re-sieving the small primes over and over again. (also what range roughly are you generating primes in)?
1 Like
Thanks for thinking about this with me. I sieve from 2-10^8, then 10^8 to 2 * 10^8, 2 * 10^8 to 3*10^8 … 10^16.
oh yeah, you’re wasting a ridiculous amount of time here. This approach requires sieving the 2-10^7 range 10^8 times (since to sieve the range p-q you need to first get all the primes less than sqrt(q)).
3 Likes
Aside from speed, a feature that would be good for me, though I’m not sure how many others would benefit by it, would be if the sieve could pause after an array is create (which would allow me to process the array and save results), before the sieve continued on. One reason for the inefficiency in my work is I must tell the sieve where to resume at some high value, like, 127 * 10^14, so it takes a lot of time to re-sieve to a proper value. I hope I"m making sense.
Exactly so.
The better interface than that I think is an iterator that yields primes 1 at a time. This can be made relatively easy and will let you sieve the whole range and process it as you need.
2 Likes
Python where?
2 Likes
I believe there is a python wrapper for Primesieve.
In this context, “other languages” including “Python”? I’m sure there’s wrapper, but like, that’s not what you mean in the “other languages with much faster prime number generators” right?
1 Like
Question: Would a prime by prime generator also be able to start at a large value before beginning prime by prime? That way I could have multiple threads starting at different values…
GitHub - shlomif/primesieve-python: Fast prime number generator. Python bindings for the primesieve C++ library The link at the bottom of the page I posted. Python bindings.
I believe that will make you re-sieve a lot again, I don’t think you want to parallel this way
2 Likes
That’s a good point. I suppose I could parallelize on the process side.