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


 
# syntax: GAWK -f PRIMALITY_BY_WILSONS_THEOREM.AWK
# converted from FreeBASIC
BEGIN {
    start = 2
    stop = 200
    for (i=start; i<=stop; i++) {
      if (is_wilson_prime(i)) {
        printf("%5d%1s",i,++count%10?"":"\n")
      }
    }
    printf("\nWilson primality test range %d-%d: %d\n",start,stop,count)
    exit(0)
}
function is_wilson_prime(n,  fct,i) {
    fct = 1
    for (i=2; i<=n-1; i++) {
      # because (a mod n)*b = (ab mod n)
      # it is not necessary to calculate the entire factorial
      fct = (fct * i) % n
    }
    return(fct == n-1)
}
 