My best implementation of Eratosthenes sieve is here.

`EratosthenesSieve[n_Integer?Positive] := Module[{lst = Range[2, n]}, Do[ If[Positive@lst[[i]],Part[lst, Range[i^2 + 2 i, n - 1, lst[[i]]]] = 0], {i, Floor[Sqrt[n + 0.0]]}]; Pick[lst, Unitize@lst, 1]] `

Now we can make a list of primes < 120.

`EratosthenesSieve[120] (*{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113}*) `

I was able to make a compiled version of the above, and you will see it doesn’t have MainEvaluate in the CompiledFunction. My compiled version is here.

`Needs["CompiledFunctionTools`"]; EratosthenesSieveC=Compile[{{n,_Integer}},Module[{lst=Range[2,n]}, Do[If[Positive@lst[[i]], Do[Part[lst,j]=0,{j,Range[i^2+2i,n-1,lst[[i]]]}]],{i,Floor[Sqrt[n+0.0]]} ]; Complement[lst,{0}] ]]; CompilePrint[EratosthenesSieveC] `

However, the compiled version is slower than my version that isn’t compiled. Is there a way to make EratosthenesSieve faster?