# Fast Generation of Arrays of Prime Numbers

**URL:** <https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120>\
**Category:** Offtopic\
**Created:** [July 3, 2023, 12:09pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120 "2023-07-03T12:09:16Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![HexSpin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexspin/32/19319_2.png) [@HexSpin](https://discourse.julialang.org/u/HexSpin)\
**Post date:** [July 3, 2023, 12:09pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/1 "2023-07-03T12:09:16Z")

</div>

I believe Primes.jl is not nearly as fast as prime number generators available in other languages, such as [PrimeSieve.org](http://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?

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [July 3, 2023, 12:13pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/2 "2023-07-03T12:13:52Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [July 3, 2023, 12:14pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/3 "2023-07-03T12:14:41Z")

</div>

the prime sieve in primes.jl is far from optional. [FastPrimeSieve · Julia Packages](https://juliapackages.com/p/fastprimesieve) 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.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [July 3, 2023, 12:18pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/4 "2023-07-03T12:18:36Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![HexSpin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexspin/32/19319_2.png) [@HexSpin](https://discourse.julialang.org/u/HexSpin)\
**Post date:** [July 3, 2023, 12:27pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/5 "2023-07-03T12:27:30Z")

</div>

Yes.

---

<div class="post-metadata">

**Author:** ![HexSpin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexspin/32/19319_2.png) [@HexSpin](https://discourse.julialang.org/u/HexSpin)\
**Post date:** [July 3, 2023, 12:28pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/6 "2023-07-03T12:28:11Z")

</div>

Get cracking! 😉

---

<div class="post-metadata">

**Author:** ![HexSpin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexspin/32/19319_2.png) [@HexSpin](https://discourse.julialang.org/u/HexSpin)\
**Post date:** [July 3, 2023, 12:31pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/7 "2023-07-03T12:31:06Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [July 3, 2023, 12:34pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/8 "2023-07-03T12:34:45Z")

</div>

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)?

---

<div class="post-metadata">

**Author:** ![HexSpin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexspin/32/19319_2.png) [@HexSpin](https://discourse.julialang.org/u/HexSpin)\
**Post date:** [July 3, 2023, 12:37pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/9 "2023-07-03T12:37:01Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [July 3, 2023, 12:41pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/10 "2023-07-03T12:41:51Z")

</div>

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)).

---

<div class="post-metadata">

**Author:** ![HexSpin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexspin/32/19319_2.png) [@HexSpin](https://discourse.julialang.org/u/HexSpin)\
**Post date:** [July 3, 2023, 12:45pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/11 "2023-07-03T12:45:05Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![HexSpin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexspin/32/19319_2.png) [@HexSpin](https://discourse.julialang.org/u/HexSpin)\
**Post date:** [July 3, 2023, 12:46pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/12 "2023-07-03T12:46:09Z")

</div>

Exactly so.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [July 3, 2023, 12:46pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/13 "2023-07-03T12:46:52Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [July 3, 2023, 12:54pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/14 "2023-07-03T12:54:47Z")

</div>

> [@HexSpin](#):
>
> [PrimeSieve.org](http://PrimeSieve.org) (Python version).

Python where?  
 ![image](https://global.discourse-cdn.com/julialang/original/3X/d/6/d6e7507d05b74b6ef44240e67f4049fb3e0b8760.png)

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [July 3, 2023, 12:56pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/15 "2023-07-03T12:56:30Z")

</div>

I believe there is a python wrapper for Primesieve.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [July 3, 2023, 12:57pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/16 "2023-07-03T12:57:11Z")

</div>

> [@HexSpin](#):
>
> I believe Primes.jl is not nearly as fast as prime number generators available in other languages, such as [PrimeSieve.org](http://PrimeSieve.org) (Python version).

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?

---

<div class="post-metadata">

**Author:** ![HexSpin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexspin/32/19319_2.png) [@HexSpin](https://discourse.julialang.org/u/HexSpin)\
**Post date:** [July 3, 2023, 12:57pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/17 "2023-07-03T12:57:35Z")

</div>

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…

---

<div class="post-metadata">

**Author:** ![HexSpin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexspin/32/19319_2.png) [@HexSpin](https://discourse.julialang.org/u/HexSpin)\
**Post date:** [July 3, 2023, 12:59pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/18 "2023-07-03T12:59:23Z")

</div>

[GitHub - shlomif/primesieve-python: Fast prime number generator. Python bindings for the primesieve C++ library](https://github.com/shlomif/primesieve-python) The link at the bottom of the page I posted. Python bindings.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [July 3, 2023, 12:59pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/19 "2023-07-03T12:59:27Z")

</div>

> [@HexSpin](#):
>
> That way I could have multiple threads starting at different values…

I believe that will make you re-sieve a lot again, I don’t think you want to parallel this way

---

<div class="post-metadata">

**Author:** ![HexSpin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hexspin/32/19319_2.png) [@HexSpin](https://discourse.julialang.org/u/HexSpin)\
**Post date:** [July 3, 2023, 1:00pm UTC](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120/20 "2023-07-03T13:00:35Z")

</div>

That’s a good point. I suppose I could parallelize on the process side.

[Next page](https://discourse.julialang.org/t/fast-generation-of-arrays-of-prime-numbers/101120.md?page=2)