On Thursday, February 13, 2014 10:47:52 AM UTC-5, Stefan Karpinski wrote:
>
> Hmm. I guess there's probably a fair amount of overhead from all that
> BitArray twiddling. I wonder if we should switch to using a full array of
> integers in the algorithm for smaller N. The BitArray thing is mostly good
> for large N where the list of primes is going to be much smaller than the
> list of integers that's produced.
>
Yes, if you use ones(Bool, N) it is about 2x faster than if you use a
BitArray on my machine, although the BitArray does save a factor of 8 in
memory in the present case. My code, for reference:
function primes2(N)
sieveTo = isqrt(N)
S = ones(Bool, N)
S[1] = 0
for i in 1:sieveTo
if S[i]
for j in i*i:i:N
S[j] = 0
end
end
end
return(sum(S))
end
