检查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测试,您可以在维基百科中查找:

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