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


include "cowgol.coh";
 
# Wilson primality test
sub wilson(n: uint32): (out: uint8) is
    out := 0;
    if n >= 2 then
        var facmod: uint32 := 1;
        var ct := n - 1;
        while ct > 0 loop
            facmod := (facmod * ct) % n;
            ct := ct - 1;
        end loop;
        if facmod + 1 == n then
            out := 1;
        end if;
    end if;
end sub;
 
# Print primes up to 100 according to Wilson
var i: uint32 := 1;
while i < 100 loop
    if wilson(i) == 1 then
        print_i32(i);
        print_char(' ');
    end if;
    i := i + 1;
end loop;
print_nl();