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.
On Thu, Feb 13, 2014 at 10:45 AM, Steven G. Johnson <[email protected]>wrote: > > > On Thursday, February 13, 2014 10:34:32 AM UTC-5, Stefan Karpinski wrote: >> >> Did you code this up in Python too? There's a built-in Julia function >> called primes (written in pure >> Julia<https://github.com/JuliaLang/julia/blob/master/base/primes.jl>), >> which implements a prime number sieve efficiently: >> >> julia> @time primes(10000000); >> elapsed time: 0.167461201 seconds (6581064 bytes allocated) >> >> Obviously the times are apples to oranges since we're on different >> machines, but it looks to be comparable to your C version. Also, on my >> system, your version runs in much less time: >> > > Note that the built-in primes function actually returns a list of primes, > rather than just counting the number of primes via an array of bits, so it > is a bit slower. On my machine it is about 2x slower than my optimized > version of James' code. >
