# Iterating over primes

**URL:** <https://discourse.julialang.org/t/iterating-over-primes/128556>\
**Category:** New to Julia\
**Tags:** iterators\
**Created:** [April 30, 2025, 8:01am UTC](https://discourse.julialang.org/t/iterating-over-primes/128556 "2025-04-30T08:01:53Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![JADekker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jadekker/32/210281_2.png) [@JADekker](https://discourse.julialang.org/u/JADekker)\
**Post date:** [April 30, 2025, 8:01am UTC](https://discourse.julialang.org/t/iterating-over-primes/128556/1 "2025-04-30T08:01:53Z")

</div>

In Project Euler, prime numbers come up quite a lot, but sometimes it is not clear how many prime numbers are needed. To avoid duplicate calculations, and as a challenge to get a bit more familiar with iterators in julia, I’ve written a struct that computes the next prime number as it is needed and then internally stores the vector of all primes so far, such that these calculations do not need to happen more than once. I’m aware that growing vectors with `push!` is not very nice, is there another more efficient way (in base julia!) to do what I’m doing? (Purely to help me become more aware of iterator practices, I’m aware of Primes.jl and the likes).

```julia
using BenchmarkTools

struct Primes
    primes_vec::Vector{Int}
end
Primes() = Primes([2,3])
function Base.iterate(P::Primes, state=1) 
    if state > length(P.primes_vec) 
        next_prime!(P)
    end
    return (P.primes_vec[state], state+1)
end
function isprime(n, primes::Primes)
    for p in primes
        p > floor(Int, sqrt(n)) && return true
        n % p == 0 && return false
    end
end

""" Assumes that primes_vec contains the first primes (at least 2 and 3) and adds the next prime by a simple sieve. """
function next_prime!(primes::Primes)
    n = primes.primes_vec[end] + 2
    while true
        if isprime(n, primes)
            push!(primes.primes_vec, n)
            return
        end
        n += 2
    end
end

function test_primes()
    P = Primes()
    @time sum(Iterators.take(P, 100_000)) # Here, we need to compute the first 100_000 primes
    @time sum(Iterators.take(P, 100_000)) # Here, we can re-use them from memory. 
end
test_primes()

```

Gives

```julia
  0.062785 seconds (10 allocations: 1.828 MiB)
  0.000066 seconds

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [April 30, 2025, 8:14am UTC](https://discourse.julialang.org/t/iterating-over-primes/128556/2 "2025-04-30T08:14:15Z")

</div>

The `nextprime` function works more or less like an iterator: [Functions · Primes.jl](https://juliamath.github.io/Primes.jl/stable/api/#Primes.nextprime) I think it avoids storing anything.

Even if you don’t want to depend on Primes.jl, you could study it.

---

<div class="post-metadata">

**Author:** ![JADekker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jadekker/32/210281_2.png) [@JADekker](https://discourse.julialang.org/u/JADekker)\
**Post date:** [April 30, 2025, 8:27am UTC](https://discourse.julialang.org/t/iterating-over-primes/128556/3 "2025-04-30T08:27:06Z")

</div>

I see, thank you! The way I understood that one is that it would recompute the primes already computed so far (as it doesn’t store anything). My point was to try and avoid unnecessary recomputations. (I’m aware that the computations are cheap here, but let’s imagine I’ll do the same with a different kind of sequence that is computationally expensive to compute)

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [April 30, 2025, 8:40am UTC](https://discourse.julialang.org/t/iterating-over-primes/128556/4 "2025-04-30T08:40:05Z")

</div>

I don’t know that much about primes, but `nextprime` calls the `isprime` function, which does not need to compute all the previous primes.

Prime numbers are probably the most heavily studied subject in all of mathematics, so I expect there are advanced methods for determining primality.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [April 30, 2025, 8:45am UTC](https://discourse.julialang.org/t/iterating-over-primes/128556/5 "2025-04-30T08:45:08Z")

</div>

…but if your main goal is to investigate iterators and accumulating stored intermediate results, then, firstly, I would point out that `push!` is not so inefficient. It preallocates more space than you ask for to avoid resizing on each step. You can also use `sizehint!` if you have a good hunch how much space you will eventually need (for example if you want to calculate 100\_000 primes, you know how much space to set aside.)

Concerning primes again:

> [@JADekker](#):
>
> `p > floor(Int, sqrt(n)) && return true`

This one is dangerous, and can give wrong answers, due to floating point issues. Use `isqrt` instead. Prime calculations inherently deal with integers, so you should avoid going through float operations.

---

<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:** [April 30, 2025, 8:45am UTC](https://discourse.julialang.org/t/iterating-over-primes/128556/6 "2025-04-30T08:45:57Z")

</div>

> [@JADekker](#):
>
> ```julia
> function Base.iterate(P::Primes, state=1) 
> if state > length(P.primes_vec) 
> next_prime!(P)
> end
> return (P.primes_vec[state], state+1)
> end
> 
> ```

This is an interesting kind of iterator, in that it’s a stateful iterator, but only as a performance optimization!

I don’t think you’re doing anything wrong, but here are two slightly different approaches you could have taken:

- Make it a purely stateless iterator, by storing the already computed primes in the iteration state (the second return value).
- Lock when updating the iterator, to be concurrency-safe.

---

<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:** [April 30, 2025, 8:50am UTC](https://discourse.julialang.org/t/iterating-over-primes/128556/7 "2025-04-30T08:50:15Z")

</div>

> [@DNF](#):
>
> I don’t know that much about primes, but `nextprime` calls the `isprime` function, which does not need to compute all the previous primes.

AFAIK, once one’s in bigint land, using a sieve (so storing all primes) is much faster than using `nextprime` repeatedly.

---

<div class="post-metadata">

**Author:** ![JADekker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jadekker/32/210281_2.png) [@JADekker](https://discourse.julialang.org/u/JADekker)\
**Post date:** [April 30, 2025, 8:59am UTC](https://discourse.julialang.org/t/iterating-over-primes/128556/8 "2025-04-30T08:59:48Z")

</div>

I see the approach to working purely stateless, but my point is that I wish to re-use the same iterator at a later point and benefit from the work already done

e.g. see how

```julia
@time sum(Iterators.take(P, 100_000)) # Here, we need to compute the first 100_000 primes
@time sum(Iterators.take(P, 100_000)) # Here, we can re-use them from memory. 

```

produces the following, where the second run is re-using the work done in the first run

```julia
  0.062785 seconds (10 allocations: 1.828 MiB)
  0.000066 seconds

```

---

<div class="post-metadata">

**Author:** ![JADekker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jadekker/32/210281_2.png) [@JADekker](https://discourse.julialang.org/u/JADekker)\
**Post date:** [April 30, 2025, 9:01am UTC](https://discourse.julialang.org/t/iterating-over-primes/128556/9 "2025-04-30T09:01:03Z")

</div>

Thanks, I didn’t think about that!

---

<div class="post-metadata">

**Author:** ![Sevi](https://avatars.discourse-cdn.com/v4/letter/s/c67d28/32.png) [@Sevi](https://discourse.julialang.org/u/Sevi)\
**Post date:** [April 30, 2025, 9:44am UTC](https://discourse.julialang.org/t/iterating-over-primes/128556/10 "2025-04-30T09:44:29Z")

</div>

If you work with primes a lot and also want save time between Julia sessions, you could also push the computation of primes to the compilation step and keep a “global” list of primes around. The list gets generated once when your package is compiled and could then be used (and expanded) during a session.

I believe this is what base Julia is doing for combinatorial factors up to a certain size:

> <https://github.com/JuliaLang/julia/blob/1f1839129b6efbf6f280b56d71f761642763a445/base/combinatorics.jl#L5C1-L20C1>

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [April 30, 2025, 10:28am UTC](https://discourse.julialang.org/t/iterating-over-primes/128556/11 "2025-04-30T10:28:21Z")

</div>

> [@DNF](#):
>
> > [@JADekker](#):
> >
> > `p > floor(Int, sqrt(n)) && return true`
> 
> This one is dangerous, and can give wrong answers, due to floating point issues. Use `isqrt` instead. Prime calculations inherently deal with integers, so you should avoid going through float operations.

Or faster, `p^2 > n`, unless overflow is an issue.

> [@JADekker](#):
>
> I see the approach to working purely stateless, but my point is that I wish to re-use the same iterator at a later point and benefit from the work already done

You can make a stateless base iterator, and make it stateful via `Iterators.Stateful`.

---

<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:** [April 30, 2025, 2:47pm UTC](https://discourse.julialang.org/t/iterating-over-primes/128556/12 "2025-04-30T14:47:38Z")

</div>

As one of the main developers of Primes.jl the basic things you are missing for performance are as follows:

1. Fast `isprime` checking (look up Baillie–PSW or Miller-Rabin). For an n bit number, these methods are ~O(n^3) as opposed to O(2^n) of trial division
2. Sieve methods rather than spending time testing whether each number is prime individually, we can compute all the primes up to `n` in roughly O(n) operations.