Проверка на первичность в Форт

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

Если этот тест говорит, что число составное, то оно определенно составное. Если он говорит, что число простое, то оно ВЕРОЯТНО простое, но несколько составных чисел будут проскальзывать (такие числа называются "псевдослучайными"). Тест достаточно быстрый и достаточный для некоторых целей.

Код, который вы опубликовали, тестирует делители 2,3,4,5,... вплоть до квадратного корня из n, и он будет примерно в 2 раза быстрее, если тестировать 2,3,5,7... так как в этом нет необходимости проверить даже делители больше 2.