Essays/Primes Less Than n

Generate the sorted list of all primes less than n . For example, 2 3 5 7 are all the primes less than 10 .

p:

p0=: i.&.(p:^:_1)

p: i is the i-th prime, with 2=p: 0 . Therefore, p:^:_1 n is the number of primes less than n , commonly denoted π(n) in conventional notation.

Factoring

p1=: (#~ 1 = #@q:) @ }. @ i.

A number is prime if its prime factorization has length 1.

Remainder Table

p2=: (#~ 2 = +/@(0&=)@(|/~)) @ }. @ i.

A number j>0 is prime if there are exactly two numbers i such that 0=i|j . The method creates an integer table of size n,n and is impractical even for small n .

Recursion

p3=: 3 : 0
 if. 11>y do. y (>#]) 2 3 5 7 else. t,}.I. *./0<t|/i.y [ t=. p3 >.%:y end.
)

A number j is prime if for no i less than >.%:j is it true that 0=i|j , that is, not divisible by any i less than >.%:j . The method creates an integer table of size (>.(%^.)%:n),n and is impractical for moderate n .

Sieve (Crossing Out Multiples)

p4=: 3 : 0
 n=. y-1
 m=. >.%:y
 z=. y (>#]) 2 3 5 7
 b=. 1,}.n$+./(*/z)$&>(-z){.&.>1  NB. 1-origin
 while. m>j=. 1+b i. 0 do.
  b=. b+.n$(-j){.1
  z=. z,j
 end.
 z,1+I.-.b
)

b is an (n-1)-element boolean mask initially with multiples of 2, 3, 5, and 7 crossed out (1 is also crossed out). In each iteration, the index j of the first 0 in b is a prime, and multiples of j are crossed out. The iteration terminates when j is >.%:n or more. The indices of the remaining 0 entries in b are prime.

Benchmarks

Time-space numbers for each method:

		1e3		1e5		1e6
p:	p0	0.0000623	8384	0.004094	362048	0.04701	2657344
Factoring	p1	0.0035619	15296	0.468785	1704896	5.85807	13632448
Remainder Table	p2	0.0888747	5258176	-	-	-	-
Recursion	p3	0.0009674	94848	0.817924	42799104	-	-
Sieve	p4	0.0005104	12416	0.089199	461632	3.02414	3673408

Collected Definitions

p0=: i.&.(p:^:_1)

p1=: (#~ 1 = #@q:) @ }. @ i.

p2=: (#~ 2 = +/@(0&=)@(|/~)) @ }. @ i.

p3=: 3 : 0
 if. 11>y do. y (>#]) 2 3 5 7 else. t,}.I. *./0<t|/i.y [ t=. p3 >.%:y end.
)

p4=: 3 : 0
 n=. y-1
 m=. >.%:y
 z=. y (>#]) 2 3 5 7
 b=. 1,}.n$+./(*/z)$&>(-z){.&.>1  NB. 1-origin
 while. m>j=. 1+b i. 0 do.
  b=. b+.n$(-j){.1
  z=. z,j
 end.
 z,1+I.-.b
)

---

Contributed by Roger Hui.