在Forth中检查素性

Question

如何在Forth中检查primality？

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

: 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的因子也不需要测试。