I used the wikipedia spanish version and algorithm, I didn't notice that it's a different one in the english version:
* https://es.wikipedia.org/wiki/Criba_de_Atkin#Pseudoc.C3.B3digo I'll check that one too. El domingo, 28 de junio de 2015, 10:16:16 (UTC-5), Ismael VC escribió: > > Hello everyone! > > I’ve implemented this Sieve of Atkin: > > - https://gist.github.com/Ismael-VC/179790a53c549609b3ce > > 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 > > Ported directly from the Wikipedia pseudocode: > > - https://en.wikipedia.org/wiki/Sieve_of_Atkin#Pseudocode > > And I’ve also compared atkin with Base.primes (IJulia notebook tested at > JuliaBox version 0.4.0-dev+5491): > > - http://nbviewer.ipython.org/gist/Ismael-VC/25b1a0c1e11f306a40ae > > I also tested it on a Mac: > > ulia> versioninfo() > Julia Version 0.3.9 > Commit 31efe69 (2015-05-30 11:24 UTC) > Platform Info: > System: Darwin (x86_64-apple-darwin13.4.0) > CPU: Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz > WORD_SIZE: 64 > BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Sandybridge) > LAPACK: libopenblas > LIBM: libopenlibm > LLVM: libLLVM-3.3 > > julia> gc(); @time primes(1000_000_000); > elapsed time: 72.423236327 seconds (531889264 bytes allocated, 0.02% gc time) > > julia> gc(); @time atkin(1000_000_000); > elapsed time: 27.908726228 seconds (2342278320 bytes allocated, 0.17% gc time) > > julia> gc(); @time primes(10_000_000_000); > elapsed time: 809.601231674 seconds (4890727200 bytes allocated, 0.00% gc > time) > > julia> gc(); @time atkin(10_000_000_000); > elapsed time: 332.286719798 seconds (160351721104 bytes allocated, 0.32% gc > time) > > Reference: > > - > https://github.com/JuliaLang/julia/issues/11594#issuecomment-115915833 > > I’m trying to understand how does Base.primes and the Base.primesmask > functions work and also how is it that atkin performs better in time (and > sometimes also in space) than Base.primes in this tests. > >
