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


import strutils, sugar
 
proc facmod(n, m: int): int =
  ## Compute (n - 1)! mod m.
  result = 1
  for k in 2..n:
    result = (result * k) mod m
 
func isPrime(n: int): bool = (facmod(n - 1, n) + 1) mod n == 0
 
let primes = collect(newSeq):
               for n in 2..100:
                 if n.isPrime: n
 
echo "Prime numbers between 2 and 100:"
echo primes.join(" ")