CODEWITHSUNDEEP
primesforthgforth
Frederik H
Frederik H

Reputation: 1506

Checking for primality in Forth

How can I check for primality in Forth?

Here is what I use now, but it gets slow with higher numbers:

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

Upvotes: 2

Views: 444

Answers (1)

none
none

Reputation: 61

A simple probabilistic method is with the Fermat test, which you can look up in Wikipedia:

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

If this test says the number is composite, then it is definitely composite. If it says the number is prime, then it is PROBABLY prime, but a few composite numbers will slip through (such numbers are called "pseudoprimes"). The test is quite fast and sufficient for some purposes.

The code you posted tests divisors 2,3,4,5,... up to the square root of n, and it would be about 2x as fast if it tested 2,3,5,7... since there's no need to test even divisors larger than 2.

Upvotes: 6

Related Questions