소수성 검사하기

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

이 테스트에서 번호가 복합이라고 말하면 분명히 복합입니다. 숫자가 소수라고하면 소수 일 것입니다. 그러나 합성 숫자가 빠져 나올 것입니다 (이러한 숫자를 "가짜 의사 (pseudoprimes)"라고합니다). 이 테스트는 일부 목적을 위해서는 상당히 빠르고 충분합니다.

게시 한 코드는 n의 제곱근까지 제수 2, 3, 4, 5 ...를 테스트했으며 2,3,5,7을 테스트하면 약 2 배 빠릅니다. [Rosetta Code] (http://rosettacode.org/wiki/Primality_by_trial_division#Forth)에 대해 들어 보셨습니까?