versioninfo()
Julia Version 0.4.0-dev+5491 Commit cb77503 (2015-06-21 09:45 UTC) Platform Info: System: Linux (x86_64-unknown-linux-gnu) CPU: Intel(R) Xeon(R) CPU E5-2670 v2 @ 2.50GHz WORD_SIZE: 64 BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Sandybridge) LAPACK: libopenblas LIBM: libopenlibm LLVM: libLLVM-3.3
module Sieves
export atkin, eratosthenes
function atkin(limit::Int = 0)
@inbounds begin
primes = [2, 3]
if limit < 0
error("limit can't be negative (found $(limit))")
elseif limit < 2
primes = Int[]
elseif limit == 2
primes = [2]
else
factor = round(Int, sqrt(limit))
sieve = falses(limit)
for x = 1:factor
for y = 1:factor
n = 4x^2 + y^2
if n <= limit && (n % 12 == 1 || n % 12 == 5)
sieve[n] = !sieve[n]
end
n = 3x^2 + y^2
if n <= limit && n % 12 == 7
sieve[n] = !sieve[n]
end
n = 3x^2 - y^2
if x > y && n <= limit && n % 12 == 11
sieve[n] = !sieve[n]
end
end
end
for x = 5:factor
if sieve[x]
for y = x^2 : x^2 : limit
sieve[y] = false
end
end
end
for i = 5:limit
if sieve[i]
push!(primes, i)
end
end
end
end
return primes
end
function eratosthenes(limit::Int = 0)
@inbounds begin
isprime = trues(limit)
isprime[1] = false
factor = round(Int, sqrt(limit))
for i in 2:factor
if isprime[i]
for j in (i*i) : i : limit
isprime[j] = false
end
end
end
return filter(x -> isprime[x], 1:limit)
end
end
end
using Sieves
funcs = [primes, atkin, eratosthenes]
for f in funcs
precompile(f, (Int,))
end
limit = 100_000_000
100000000
primes(limit) == atkin(limit) == eratosthenes(limit)
true
function test(f, n)
for i = 1:10
gc()
@time f(n)
gc()
end
end
test (generic function with 1 method)
test(primes, limit)
3.519 seconds (9042 k allocations: 194 MB, 0.24% gc time) 3.516 seconds (9042 k allocations: 194 MB, 0.22% gc time) 3.553 seconds (9042 k allocations: 194 MB, 0.22% gc time) 3.528 seconds (9042 k allocations: 194 MB, 0.22% gc time) 3.518 seconds (9042 k allocations: 194 MB, 0.22% gc time) 3.515 seconds (9042 k allocations: 194 MB, 0.23% gc time) 3.514 seconds (9042 k allocations: 194 MB, 0.22% gc time) 3.514 seconds (9042 k allocations: 194 MB, 0.22% gc time) 3.514 seconds (9042 k allocations: 194 MB, 0.23% gc time) 3.514 seconds (9042 k allocations: 194 MB, 0.22% gc time)
test(atkin, limit)
2.038 seconds (20 allocations: 78768 KB, 0.03% gc time) 2.037 seconds (20 allocations: 78768 KB, 0.03% gc time) 2.036 seconds (20 allocations: 78768 KB, 0.03% gc time) 2.036 seconds (20 allocations: 78768 KB, 0.03% gc time) 2.037 seconds (20 allocations: 78768 KB, 0.03% gc time) 2.036 seconds (20 allocations: 78768 KB, 0.03% gc time) 2.036 seconds (20 allocations: 78768 KB, 0.03% gc time) 2.036 seconds (20 allocations: 78768 KB, 0.03% gc time) 2.037 seconds (20 allocations: 78768 KB, 0.03% gc time) 2.037 seconds (20 allocations: 78768 KB, 0.03% gc time)
test(eratosthenes, limit)
7.277 seconds (100000 k allocations: 1677 MB, 1.62% gc time) 7.290 seconds (100000 k allocations: 1677 MB, 1.69% gc time) 7.263 seconds (100000 k allocations: 1677 MB, 1.58% gc time) 7.303 seconds (100000 k allocations: 1677 MB, 1.77% gc time) 7.303 seconds (100000 k allocations: 1677 MB, 1.67% gc time) 7.272 seconds (100000 k allocations: 1677 MB, 1.58% gc time) 7.301 seconds (100000 k allocations: 1677 MB, 1.60% gc time) 7.333 seconds (100000 k allocations: 1677 MB, 1.71% gc time) 7.312 seconds (100000 k allocations: 1677 MB, 1.75% gc time) 7.320 seconds (100000 k allocations: 1677 MB, 1.77% gc time)