Sieve of Eratosthenes

Author

Eric W. Weisstein
May 26, 2022

This notebook downloaded from http://mathworld.wolfram.com/notebooks/PrimeNumbers/SieveofEratosthenes.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/SieveofEratosthenes.html.

©2022 Wolfram Research, Inc. except for portions noted otherwise

Graphic

Factors[n_]:=First/@FactorInteger[n]

EratosthenesSieve[x_Integer?Positive,y_Integer?Positive,max_:Infinity,opts___]:=Module[{num,facs,i,j,k,n,yoff=0.4,ystart=0.3,xoff=0.3,xsep=0.25,slashes={}},num=Table[Text[i+(j-1)*x,{i,-j}],{j,1,y},{i,1,x}];
For[j=1,j≤y,j++,For[i=1,i≤x,i++,n=i+(j-1)*x;
If[!PrimeQ[n],facs=Factors[n];
k=1;
While[k≤Length[facs]&&facs[[k]]≤max,k++];
facs=Take[facs,k-1];
len=Length[facs];
For[k=1,k≤len,k++,xpos=i+(k-1-.5(len-1))xsep;
slashes=Append[slashes,{Text[FontForm[facs[[k]],{"Times-Roman",9}],{xpos,-j-yoff}],Line[{{xpos,-j-ystart},{xpos,-j+ystart}}]}];]]]];
Graphics[{num,slashes},PlotRange->All,AspectRatio->Automatic,opts]]

EratosthenesSieveArray[x_Integer?Positive,y_Integer?Positive,n_Integer]:=Show[GraphicsArray[Partition[Table[EratosthenesSieve[10,5,Prime[i],DisplayFunction->Identity],{i,1,n}],2]],DisplayFunction->$DisplayFunction]

EratosthenesSieveArray[10,5,4]

Algorithms

Compiled

Xiangdong Wen
May 26, 2022

primeslist=FunctionCompile[Function[Typed[arg,"MachineInteger"],Module[{ans},ans=Range[arg];
ans[[1]]=0;
Do[If[ans[[p]]==p,Do[ans[[i]]=0,{i,p*p,arg,p}]],{p,2,Floor[Power[arg,0.5]],1}];
ans]]];

primes[n_Integer]:=SparseArray[primeslist[n]]["NonzeroValues"]

primes[10^7]//Length//AbsoluteTiming

primes[10^8]//Length//AbsoluteTiming

PrimePi[{10^7,10^8}]

Reap

From Sam Blake
Feb. 21, 2007

prime[lst_,n_]:={Join[lst[[;;n]],Reap[Scan[If[!IntegerQ[#/lst[[n]]],Sow[#]]&,lst[[n;;]]]][[2,1]]],n+1}

sieve[n_]:=Rest@First@NestWhile[prime[First[#],Last[#]]&,{Range[n],2},Length[First[#]]>Last[#]&]

sieve[100]

sieve[10^4]//Length//AbsoluteTiming

Select

Select[Range[10^7],PrimeQ]//Length//AbsoluteTiming

Select[Range[10^8],PrimeQ]//Length//AbsoluteTiming

PrimePi[{10^7,10^8}]

StackExchange

https://mathematica.stackexchange.com/questions/241191/compiling-eratosthenes-sieve

primes[n_]:=Module[{p=Range[1,n,2]},p[[1]]=2;
Do[If[p[[(k+1)/2]]!=0,p[[(k^2+1)/2;; ;;k]]=0],{k,3,n^.5,2}];
SparseArray[p]["NonzeroValues"]]

primes[10^7]//Length//AbsoluteTiming

primes[10^8]//Length//AbsoluteTiming

PrimePi[{10^7,10^8}]