Проверка на простоту в Форте

Как я могу проверить основность в 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 ;

forth primes gforth
person Frederik H    schedule 09.11.2012    source источник
comment
Вы слышали о Rosetta Code?   -  person Will Ness    schedule 10.11.2012
comment
Вы просите предложить более быстрый алгоритм или пример реализации?   -  person sheepez    schedule 20.11.2012

Ответы (1)


arrow_upward
5
arrow_downward

Простой вероятностный метод — это тест Ферма, который вы можете найти в Википедии:

: *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.

person none    schedule 22.11.2012
comment
Когда составные части проскальзывают, тогда требуется полный первичный тест, но поскольку к этому моменту исключается большое количество чисел, вы хороши на практике, верно? - person RonaldBarzell; 05.12.2012