primes - 埃拉托色尼 (Eratosthenes) 的 J(默认)筛

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

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

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

问候，
巴布斯博士

最佳答案

这不完全是你要问的，但这里有一个更惯用的( 比快得多)版本的 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

每对倍数在表上给出一个 0。现在，我们对对应于自模(2 mod 2、3 mod 3 等；对角线上的 0 )的 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 感兴趣。因此，在构建表时，我们将通过取每个数字的“符号”(这是 0 : 1 )只保留 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

所以，

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

从排除列表中，您只需将 copy : # 数字添加到最终列表中:

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

或者，

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

关于primes - 埃拉托色尼 (Eratosthenes) 的 J(默认)筛，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13608950/