Differences between revisions 11 and 12
 ⇤ ← Revision 11 as of 2007-10-01 17:56:52 → Size: 2861 Editor: RogerHui Comment: collected defns ← Revision 12 as of 2008-12-08 10:45:30 → ⇥ Size: 2861 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 7: Line 7: [[TableOfContents(2)]] <> Line 102: Line 102: [[BR]] <
>

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
)```

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:

 1000 1e5 1e6 p: p0 6.23e-05 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 RogerHui.

Essays/Primes Less Than n (last edited 2008-12-08 10:45:30 by anonymous)