using Base.Threads

@show nthreads()
versioninfo()

# @threads を削除すれば、シングルスレッドで動作する
# ６スレッドでシングルスレッドの約２倍しか速くならない

function sieve!(x::AbstractVector{Bool})
    #all(x) || fill!(x, true)
    n = length(x)
    x[1] = false
    @inbounds for p in 2:isqrt(n)
        x[p] || continue
        @threads for i in p^2:p:n
            x[i] && (x[i] = false)
        end
    end
end

# Vector{Bool}
function sieve(n::Integer)
    x = ones(Bool, n)
    sieve!(x)
    x
end

# BitVector
function sieve_conflict(n::Integer)
    x = trues(n)
    sieve!(x)
    x
end

sieve(100) |> findall

# 100 以下の素数は 25 のはずだが、 BitVector を使った場合は増えることがある
[count(sieve_conflict(100)) for _ in 1:300] |> print

function bench(f, ks=5:9)
    println(f)
    for k in ks
        stats = @timed f(10^k)
        println("n=10^$k\t$(stats.time) sec\t$(stats.bytes) bytes")
    end
    println()
end

bench(sieve)
bench(sieve_conflict)

@time sieve(10^10) |> count |> ==(455052511)

# Atomic
function sieve_atomic(n::Integer)
    x = [Atomic{Bool}(true) for _ in 1:n]
    x[1][] = false
    @inbounds for p in 2:isqrt(n)
        x[p][] || continue
        @threads for i in p^2:p:n
            atomic_cas!(x[i], true, false)
        end
    end
    getindex.(x)
end

# 素直に配列を使ったほうが速い
bench(sieve_atomic, 5:8)