J（隐式）埃拉托斯特尼筛法

Question

J（隐式）埃拉托斯特尼筛法

primesjsieve-of-eratosthenes

3

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

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

因此，输出结果是2 3 5 7 61。基本上是Eratosthenes筛法。如果有人能解释代码，那就太好了，因为我正在学习J，并发现大多数代码很难理解。

敬礼， babsdoc

- babsdoc

2个回答

2

暗示迭代通常与 Power结合使用。当完成测试需要的内容不是命中一个固定点时， Do While结构很有效。

在这个解决方案中，filterMultiplesOfHead被重复应用，直到没有更多未应用或过滤的数字。已经应用的数字在部分答案中累积。当要处理的列表为空时，部分答案就是结果，需要去掉用于隔离已处理和未处理数据的包装。

   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

- kaleidic

1

我正在执行 sieve 1-.~/:~~.>:?$~100，但是我得到了一些不应该得到的倍数。我看不出为什么... - Eelvex

2

我原始发布的只过滤了素数因子，这是不正确的。我已经更改为过滤掉每个被检查数字作为因子的数字。感谢您提醒我存在的问题。 - kaleidic

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eelvex · Accepted Answer

虽然不完全符合您的要求，但这里提供了一个更习惯用语和快得多的筛法版本。

基本上，您需要检查哪个数字是哪个数字的倍数。您可以从模表中获取此信息：|/~

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。现在，我们不关心与自身模数相对应的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 和非 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