Task

Write a boolean function that tells whether a given integer is prime using Wilson's theorem.

By Wilson's theorem, a number p is prime if and only if p divides (p - 1)! + 1.

Remember that 1 and all non-positive integers are not prime.



See also

 Cut-the-knot: Wilson's theorem.
 Wikipedia: Wilson's theorem


    PRINT "Number to test"
    INPUT N
    IF N < 0 THEN LET N = -N
    IF N = 2 THEN GOTO 30
    IF N < 2 THEN GOTO 40 
    LET F = 1
    LET J = 1
10  LET J = J + 1
    REM exploits the fact that (F mod N)*J = (F*J mod N)
    REM to do the factorial without overflowing
    LET F = F * J
    GOSUB 20
    IF J  < N - 1 THEN GOTO 10
    IF F  = N - 1 THEN PRINT "It is prime"
    IF F <> N - 1 THEN PRINT "It is not prime"
    END
20  REM modulo by repeated subtraction
    IF F < N THEN RETURN
    LET F = F - N
    GOTO 20
30  REM special case N=2
    PRINT "It is prime"
    END
40  REM zero and one are nonprimes by definition
    PRINT "It is not prime"
    END