My favorite prime number generator

He said he has "used this code many times"... have you ever needed to find prime numbers in your daily programming?

Reminds me of the time where I've implemented highly optimised version of Sieve of Eratosthenes in Java, just for a Code Golf Challenge.

Memory Usage is greatly reduced by using BitSet.

https://github.com/krnaveen14/PrimeNumbers/blob/master/src/m...

https://codegolf.stackexchange.com/a/66915/41984

OMG, it's been 8 years already!

Could you explain it? Those two links are Greek to me.

That doesn't seem like a good way to generate "random" numbers, since it will only produce numbers with exactly two prime factors.

It's an APL sieve, for an input of 15 (primes up to 15) it does these steps:

First 15 integers:

          ⍳ 15
    ┌→──────────────────────────────────┐
    │1 2 3 4 5 6 7 8 9 10 11 12 13 14 15│
    └~──────────────────────────────────┘

1 element dropped from the front of that:

          1↓⍳15
    ┌→────────────────────────────────┐
    │2 3 4 5 6 7 8 9 10 11 12 13 14 15│
    └~────────────────────────────────┘

That array stored in variable T:

          T←1↓⍳15

A table of outer-product multiplication, T by T:

          T∘.×T
    ┌→─────────────────────────────────────────────────┐
    ↓ 4  6  8 10 12  14  16  18  20  22  24  26  28  30│
    │ 6  9 12 15 18  21  24  27  30  33  36  39  42  45│
    │ 8 12 16 20 24  28  32  36  40  44  48  52  56  60│
    │10 15 20 25 30  35  40  45  50  55  60  65  70  75│
    │12 18 24 30 36  42  48  54  60  66  72  78  84  90│
    │14 21 28 35 42  49  56  63  70  77  84  91  98 105│
    │16 24 32 40 48  56  64  72  80  88  96 104 112 120│
    │18 27 36 45 54  63  72  81  90  99 108 117 126 135│
    │20 30 40 50 60  70  80  90 100 110 120 130 140 150│
    │22 33 44 55 66  77  88  99 110 121 132 143 154 165│
    │24 36 48 60 72  84  96 108 120 132 144 156 168 180│
    │26 39 52 65 78  91 104 117 130 143 156 169 182 195│
    │28 42 56 70 84  98 112 126 140 154 168 182 196 210│
    │30 45 60 75 90 105 120 135 150 165 180 195 210 225│
    └~─────────────────────────────────────────────────┘

The elements of T which exist (are found) in the multiplication table, boolean result:

          T∊T∘.×T
    ┌→──────────────────────────┐
    │0 0 1 0 1 0 1 1 1 0 1 0 1 1│
    └~──────────────────────────┘

Showing that together with the input, 4 6 8 are found, 2 3 5 are not:

          T,[0.5]T∊T∘.×T
    ┌→────────────────────────────────┐
    ↓2 3 4 5 6 7 8 9 10 11 12 13 14 15│
    │0 0 1 0 1 0 1 1  1  0  1  0  1  1│
    └~────────────────────────────────┘
    

Numbers not found in the multiplication table are prime, so invert the test result so primes get 1 and composites get 0:

    ~T∊T∘.×T
    ┌→──────────────────────────┐
    │1 1 0 1 0 1 0 0 0 1 0 1 0 0│
    └~──────────────────────────┘
    

Use that to 'compress' the input to keep things where the 1 positions are and drop things where the 0s are:

          (~T∊T∘.×T)/T
    ┌→────────────┐
    │2 3 5 7 11 13│
    └~────────────┘

You can play with it at https://tryapl.org/ using the bar at the top to enter the symbols.