primes - J(默认)埃拉托斯特尼筛法

Question

我正在寻找 J 代码来执行以下操作。

假设我有一个随机整数列表(已排序)，2 3 4 5 7 21 45 49 61我想从第一个元素开始，删除列表中该元素的任何倍数，然后移动到下一个元素，取消其倍数，依此类推。

因此输出我正在看的是 2 3 5 7 61。基本上是埃拉托斯特尼筛。如果有人也能解释代码，我将不胜感激，因为我正在学习 J 并且发现很难获得大多数代码:(

问候，babsdoc

Answer 1

这并不完全符合您的要求，但这是一个更惯用(并且更快)版本的 Sieve。

基本上，您需要检查哪个数字是哪个数字的倍数。您可以从模表中得到:|/~

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

每对倍数在 table 上都会给出一个0。现在，我们对与自模相对应的 0 不感兴趣(2 mod 2、3 mod 3 等；对角线上的 0)，因此我们必须删除它们。一种方法是在其位置添加 1，如下所示:

=/~ 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

这也可以写成(=/~ + |/~) l。

从此表中我们得到最终的数字列表:列中包含 0 的每个数字均被排除。

我们只需乘以列即可构建此排除列表。如果列包含 0，则其乘积为 0，否则为正数:

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

在执行最后一步之前，我们必须对此进行一些改进。没有理由执行长乘法，因为我们只对 0 和 not-0 感兴趣。因此，在构建表格时，我们将通过获取每个数字的“符号”(即 signum:* )来仅保留 0 和 1 :

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

所以，

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

从排除列表中，您只需复制:#号码到您的最终列表:

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

或者，

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