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


% Wilson primality test
wilson = proc (n: int) returns (bool)
    if n<2 then return (false) end 
    fac_mod: int := 1
    for i: int in int$from_to(2, n-1) do
        fac_mod := fac_mod * i // n 
    end 
    return (fac_mod + 1 = n)
end wilson 
 
% Print primes up to 100 using Wilson's theorem
start_up = proc ()
    po: stream := stream$primary_output()
    for i: int in int$from_to(1, 100) do
        if wilson(i) then   
            stream$puts(po, int$unparse(i) || " ")
        end
    end
    stream$putl(po, "")
end start_up 