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

簡単な確率的手法は、ウィキペディアで調べることができるフェルマー検定を使用することです。

: *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 = ;

このテストで数値が合成数であると示された場合、それは間違いなく合成数です。数が素数であると表示されている場合、それは確率的素数ですが、いくつかの合成数がすり抜けます（このような数は「擬素数」と呼ばれます）。テストは非常に高速で、いくつかの目的には十分です。

投稿したコードは、nの平方根まで除数2,3,4,5、...をテストします。必要がないため、2,3,5,7...をテストした場合の約2倍の速度になります。 2より大きい約数でもテストします。