Vocabulary/pco

 p: y Primes

Rank 0 -- operates on individual atoms of y, producing a result of the same shape -- WHY IS THIS IMPORTANT?

The y-th prime (starting with 2 as the 0-th prime).

```   p: i.9
2 3 5 7 11 13 17 19 23
p: 2000
17393
```

The inverse  p:^:_1 y tells the number of primes less than y

```   p:^:_1 (17 19 23 24 25)
6 7 8 9 9
```

Common uses

Mathematical investigations.

Related Primitives

 x p: y Primes

Rank Infinity -- operates on x and y as a whole -- WHY IS THIS IMPORTANT?

A collection of prime-related functions of integer y, with x selecting the function.

 The Prime Functions x p: y x Function _4 The largest prime smaller than y _1 π(y), the number of primes less than y (same as p:^:_1) 0 1 if y is not prime 1 1 if y is prime 2 a 2-row table of the prime factors and exponents in the factorization of y (same as __ q: y) 3 the list of primes whose product is equal to y (same as q: y) 4 The smallest prime larger than y 5 The number of integers less than or equal to y that are relatively prime to y (Euler's totient function φ(y))
```   ]y=: p: 2001   NB. The 2001st prime
17401

_4 p: y        NB. Next prime down from y
17393
4 p: 17393     NB. Next prime up from 17393
17401
_1 p: y        NB. Number of primes <y
2001
1 p: y         NB. Boolean: y is prime
1
0 p: y         NB. Boolean: y is non-prime
0

1 p: i.25      NB. flags the primes in i.25
0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0
I. (1 p: i.25) NB. Primes in (i.25)
2 3 5 7 11 13 17 19 23
NB. Euler's Prime-Generating Polynomial n^2 + n + 41 is
NB. known to generate (distinct) primes for n = 0..39
1 p: 41 1 1 p. i. 40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
NB. and has less than 100% success for n > 39
v=. 41 1 1 p. 39 + i. 12
(] ,:1&p:) v
1601 1681 1763 1847 1933 2021 2111 2203 2297 2393 2491 2591
1    0    0    1    1    0    1    1    1    1    0    1

3 p: 2+ 2^31   NB. prime factorization of 2+(2^31)
2 5 5 13 41 61 1321
2 p: 2+ 2^31   NB. table of prime factors of 2+(2^31) with their exponents
2 5 13 41 61 1321
1 2  1  1  1    1
3 p: !23x      NB. same for a factorial (note the use of extended precision integer)
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 5 5 5 5 7 7 7 11 11 13 17 19 23
2 p: !23x
2 3 5 7 11 13 17 19 23
19 9 4 3  2  1  1  1  1

NB. Totient function φ(y) = Number of co-prime integers less than or equal to y
NB. φ(y) = y-1 (if y is prime) and less of course if y is composite

5 p: y         NB. y (17401) is prime
17400
3 p: y-1       NB. y-1 (17400) is composite (non-prime)
2 2 2 3 5 5 29
2 p: y-1       NB. showing distinct prime factors
2 3 5 29
3 1 2  1
NB. using Product over the distinct prime factors
(y-1)*(1-1r2)*(1-1r3)*(1-1r5)*(1-1r29)
4480
NB. using Product (more elegant version from the 'Voc/Primes' section)
*/ (p-1)*p^e-1 [ 'p e'=. 2 p: y-1
4480
NB. using Product (Andrew Nikitin's version of above expression)
(- ~:) &. q: y-1
4480
5 p: y-1       NB. using Totient function shortcut
4480
```

Common uses

Mathematical investigations.

Details

1. Primality testing on numbers larger than (2^31) uses the probabilistic Miller-Rabin algorithm.