multithreaded_prime_sieve.jl

#=
This code comes mostly from the talk "JuliaCon 2019 | Multi-threading in Julia with PARTR":
https://youtu.be/HfiRnfKxI64?t=729

It is a Julia translation of this Go code:
https://github.com/thomas11/csp/blob/f2ec7c4/csp.go#765

I fixed a few errors in the Julia code:
* replaced numPrimes with n
* replaced `if m < m` with `if m < mp`
* replaced `if length(primes)==n` with `if i == n`
* replaced `n` with `k` in the last part of the function

To run this code, execute the following shell command
(set the number of threads to the number of cores on your system):
JULIA_NUM_THREADS=4 julia multithreaded_prime_sieve.jl
=#

function S61_SIEVE(n::Integer)
    done = Threads.Atomic{Bool}(false)
    primes = Int[]
    sieves = [Channel{Int}() for _ = 1:n]
    for i in 1:n
        Threads.@spawn begin
            mp = p = take!(sieves[i])
            push!(primes, p)
            if i == n
                done[] = true
                return
            end
            for m in sieves[i]
                while m > mp; mp += p; end
                if m < mp
                    put!(sieves[i + 1], m)
                end
            end
        end
    end

    put!(sieves[1], 2)
    k = 3
    while !done[]
        put!(sieves[1], k)
        k += 2
    end
    return primes
end

primes = S61_SIEVE(100)
println("Found $(length(primes)) primes:")
println(primes)