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.