# 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:

 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 Roger Hui.