Sieve of Eratosthenes iterator

New to Julia
, , ,
1

I would like to create an Iterator for prime numbers (I know there is a package Primes). Based on Pythons code for the Sieve of Eratosthenes I coded a function sieve(). sieve(10) returns a vector of the first 10 primes.

What must be done to turn this into en Iterator so that it calculates one prime at a time when you want the next prime?

Thanks for any advice! I’m quite new to Julia and coming from Python I look for an (easy) alternative for generators.

function sieve(n::Int64)::Vector{Int64}
    
    D = Dict{Int64, Vector{Int64}}()
    P = Vector{Int64}()
    q = 2
    counter = 0

    while counter < n
        if !(q in keys(D))
            D[q * q] = Int64[q] # Vector{Int64}([q])
            push!(P, q)
            counter += 1
        else
            for p in D[q]
                haskey(D, p+q) ? push!(D[p+q], p) : D[p+q] = [p]
            end
            delete!(D, q)
        end
        q += 1
    end
    return P
end
2

You can either make an iterator, i.e. define Base.iterate for a suitable struct, as in Interfaces · The Julia Language, With less boilerplate you can make a coroutine with the help of a Channel, as in Asynchronous Programming · The Julia Language. Instead of yield in the loop, you do a put! on a channel, which you can take! from elsewhere.

2 Likes