primes - 在 Forth 中检查素数

Question

如何在 Forth 中检查素数？

这是我现在使用的，但是随着数字的增加它会变慢：

: prime ( n - f )
  DUP 2 < IF 
    DROP 0 EXIT
  THEN
  DUP 2 ?DO
    DUP I I * < IF
      DROP -1 LEAVE
    THEN
    DUP I MOD 0= IF
      DROP 0 LEAVE
    THEN
  LOOP ;

Answer 1

一个简单的概率方法是使用 Fermat 测试，您可以在 Wikipedia 中查找：

: *mod ( a b n -- n2 )
    */mod drop ;

: expmod { x e n -- n2 } \ compute x^e mod n by repeated squaring
    e 0= if 1 exit
    else
        x e 2/ n recurse dup n *mod
        e 1 and if x n *mod then 
    then ;

: prime ( n -- f )
    3 swap dup expmod 3 = ;

如果这个测试说这个数字是复合的，那么它肯定是复合的。如果它说这个数字是素数，那么它很可能是素数，但是一些合数会漏掉（这样的数字被称为“伪素数”）。对于某些目的，该测试非常快速且足够。

您发布的代码测试除数 2,3,4,5,... 直到 n 的平方根，如果它测试 2,3,5,7... 的速度大约是 2 倍...因为不需要测试大于 2 的偶数除数。