primes - 在 Forth 中检查素数

Question

我如何检查 primality在 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

一种简单的概率方法是费马检验，您可以在维基百科中查找:

: *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 的除数。