J (Tacit) Sieve Of Eratosthenes

Question

I'm looking for a J code to do the following.

Suppose I have a list of random integers (sorted), 2 3 4 5 7 21 45 49 61 I want to start with the first element and remove any multiples of the element in the list then move on to the next element cancel out its multiples, so on and so forth.

Thus the output I'm looking at is 2 3 5 7 61. Basically a Sieve Of Eratosthenes. Would appreciate if someone could explain the code as well, since I'm learning J and find it difficult to get most codes :(

Regards, babsdoc

Answer 1

It's not exactly what you ask but here is a more idiomatic (and much faster) version of the Sieve.

Basically, what you need is to check which number is a multiple of which. You can get this from the table of modulos: |/~

l =: 2 3 4 5 7 21 45 49 61
|/~ l
  0 1 0 1 1  1  1  1  1
  2 0 1 2 1  0  0  1  1
  2 3 0 1 3  1  1  1  1
  2 3 4 0 2  1  0  4  1
  2 3 4 5 0  0  3  0  5
  2 3 4 5 7  0  3  7 19
  2 3 4 5 7 21  0  4 16
  2 3 4 5 7 21 45  0 12
  2 3 4 5 7 21 45 49  0

Every pair of multiples gives a 0 on the table. Now, we are not interested in the 0s that correspond to self-modulos (2 mod 2, 3 mod 3, etc; the 0s on the diagonal) so we have to remove them. One way to do this is to add 1s on their place, like so:

=/~ l
  1 0 0 0 0 0 0 0 0
  0 1 0 0 0 0 0 0 0
  0 0 1 0 0 0 0 0 0
  0 0 0 1 0 0 0 0 0
  0 0 0 0 1 0 0 0 0
  0 0 0 0 0 1 0 0 0
  0 0 0 0 0 0 1 0 0
  0 0 0 0 0 0 0 1 0
  0 0 0 0 0 0 0 0 1
(=/~l) + (|/~l)
  1 1 0 1 1  1  1  1  1
  2 1 1 2 1  0  0  1  1
  2 3 1 1 3  1  1  1  1
  2 3 4 1 2  1  0  4  1
  2 3 4 5 1  0  3  0  5
  2 3 4 5 7  1  3  7 19
  2 3 4 5 7 21  1  4 16
  2 3 4 5 7 21 45  1 12
  2 3 4 5 7 21 45 49  1

This can be also written as (=/~ + |/~) l.

From this table we get the final list of numbers: every number whose column contains a 0, is excluded.

We build this list of exclusions simply by multiplying by column. If a column contains a 0, its product is 0 otherwise it's a positive number:

*/ (=/~ + |/~) l
   256 2187 0 6250 14406 0 0 0 18240

Before doing the last step, we'll have to improve this a little. There is no reason to perform long multiplications since we are only interested in 0s and not-0s. So, when building the table, we'll keep only 0s and 1s by taking the "sign" of each number (this is the signum:*):

* (=/~ + |/~) l
  1 1 0 1 1 1 1 1 1
  1 1 1 1 1 0 0 1 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 0 1 1
  1 1 1 1 1 0 1 0 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

so,

*/ * (=/~ + |/~) l
  1 1 0 1 1 0 0 0 1

From the list of exclusion, you just copy:# the numbers to your final list:

l #~ */ * (=/~ + |/~) l
   2 3 5 7 61

or,

(]#~[:*/[:*=/~+|/~) l
   2 3 5 7 61

Answer 2

Tacit iteration is usually done with the conjunction Power. When the test for completion needs to be something other than hitting a fixpoint, the Do While construction works well.

In this solution filterMultiplesOfHead is applied repeatedly until there are no more numbers not either applied or filtered. Numbers already applied are accumulated in a partial answer. When the list to be processed is empty the partial answer is the result, after stripping off the boxing used to segregate processed from unprocessed data.

   filterMultiplesOfHead=: {. (((~: >.)@ %~) # ]) }.
   appendHead=: (>@[ , {.@>@])/
   pass=: appendHead ; filterMultiplesOfHead@>@{:
   prep=: a: , <
   unfinished=: [: -. a: -: {:
   sieve=: [: ; [: pass^:unfinished^:_ prep

   sieve 2 3 4 5 7 21 45 49 61 
2 3 5 7 61

   prep 2 3 4 7 9 10
┌┬────────────┐
││2 3 4 7 9 10│
└┴────────────┘
   appendHead prep 2 3 4 7 9 10
2
   filterMultiplesOfHead 2 3 4 7 9 10
3 7 9
   pass^:2 prep 2 3 4 7 9 10
┌───┬─┐
│2 3│7│
└───┴─┘
   sieve 1-.~/:~~.>:?.$~100
2 3 7 11 29 31 41 53 67 73 83 95 97