Prime Numbers

[jdan]

Prime Numbers

[How to read this blog post]

Today's sketch involves the prime numbers, and we'll get a glimpse of J tables, forks, and filtering by value.

NB. Grab a list of the first 10 integers
i.10
NB. 0 1 2 3 4 5 6 7 8 9

NB. We can modulo each of these items by 2
2 | i.10
NB. 0 1 0 1 0 1 0 1 0 1

NB. We can form tables using the / adverb
(i.10) */ (i.10)	   NB. A times table
NB. 0 0  0  0  0  0  0  0  0  0
NB. 0 1  2  3  4  5  6  7  8  9
NB. 0 2  4  6  8 10 12 14 16 18
NB. 0 3  6  9 12 15 18 21 24 27
NB. 0 4  8 12 16 20 24 28 32 36
NB. 0 5 10 15 20 25 30 35 40 45
NB. 0 6 12 18 24 30 36 42 48 54
NB. 0 7 14 21 28 35 42 49 56 63
NB. 0 8 16 24 32 40 48 56 64 72
NB. 0 9 18 27 36 45 54 63 72 81

NB. We can form a table using modulo instead of times
(i.10) |/ (i.10)
NB. 0 1 2 3 4 5 6 7 8 9
NB. 0 0 0 0 0 0 0 0 0 0
NB. 0 1 0 1 0 1 0 1 0 1
NB. 0 1 2 0 1 2 0 1 2 0
NB. 0 1 2 3 0 1 2 3 0 1
NB. 0 1 2 3 4 0 1 2 3 4
NB. 0 1 2 3 4 5 0 1 2 3
NB. 0 1 2 3 4 5 6 0 1 2
NB. 0 1 2 3 4 5 6 7 0 1
NB. 0 1 2 3 4 5 6 7 8 0

NB. We can use the "same" verb ] to do some light refactoring
(] i.10) |/ (] i.10)
NB. (f g h) x magically "forks" into (f x) g (h x)
(] |/ ]) i.10

NB. We can see whole divisions by checking values equal to 0
0= (] |/ ]) i.10
NB. 1 0 0 0 0 0 0 0 0 0
NB. 1 1 1 1 1 1 1 1 1 1
NB. 1 0 1 0 1 0 1 0 1 0
NB. 1 0 0 1 0 0 1 0 0 1
NB. 1 0 0 0 1 0 0 0 1 0
NB. 1 0 0 0 0 1 0 0 0 0
NB. 1 0 0 0 0 0 1 0 0 0
NB. 1 0 0 0 0 0 0 1 0 0
NB. 1 0 0 0 0 0 0 0 1 0
NB. 1 0 0 0 0 0 0 0 0 1

NB. We can count the divisors of a number by summing the rows
+/ 0= (] |/ ]) i.10
NB. 10 1 2 2 3 2 4 2 4 3

NB. Prime numbers have exactly two divisors: 1 and themselves
NB. Which of our candidates have exactly two divisors?
2= +/ 0= (] |/ ]) i.10
NB. 0 0 1 1 0 1 0 1 0 0

NB. Which indices of the array have a value of 1?
I. 2= +/ 0= (] |/ ]) i.10
NB. 2 3 5 7

NB. We can now generate primes up to n
primes =: verb : 'I. 2= +/ 0= (] |/ ]) i.y'
primes 10
NB. 2 3 5 7

primes 100
NB. 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

NB. Count the number of primes below 1000
# primes 1000
NB. 168