Primality by Wilson's theorem

Primality by Wilson's theorem is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

Write a boolean function that tells whether a given integer is prime.

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

Use Wilson's theorem.

A number is prime if p divides (p - 1)! + 1.

Go

Needless to say, Wilson's theorem is an extremely inefficient way of testing for primalty with 'big integer' arithmetic being needed to compute factorials greater than 20.

Presumably we're not allowed to make any trial divisions here except by the number two where all even positive integers, except two itself, are obviously composite. <lang go>package main

import (

   "fmt"
   "math/big"

)

var (

   zero = big.NewInt(0)
   one  = big.NewInt(1)
   prev = big.NewInt(factorial(20))

)

// Only usable for n <= 20. func factorial(n int64) int64 {

   res := int64(1)
   for k := n; k > 1; k-- {
       res *= k
   }
   return res

}

// If memo == true, stores previous sequential // factorial calculation for odd n > 21. func wilson(n int64, memo bool) bool {

   if n <= 1 || (n%2 == 0 && n != 2) {
       return false
   }
   if n <= 21 {
       return (factorial(n-1)+1)%n == 0
   }
   b := big.NewInt(n)
   r := big.NewInt(0)
   z := big.NewInt(0)
   if !memo {
       z.MulRange(2, n-1) // computes factorial from scratch
   } else {
       prev.Mul(prev, r.MulRange(n-2, n-1)) // uses previous calculation
       z.Set(prev)
   }
   z.Add(z, one)
   z.QuoRem(z, b, r)
   return r.Cmp(zero) == 0

}

func main() {

   numbers := []int64{2, 3, 9, 15, 29, 37, 47, 57, 67, 77, 87, 97, 237, 409, 659}
   fmt.Println(" n prime")
   fmt.Println("-- -----")
   for _, n := range numbers {
       fmt.Printf("%2d %t\n", n, wilson(n, false))
   }

   // sequential memoized calculation
   fmt.Println("\nThe first 120 prime numbers are:")
   for i, count := int64(2), 0; count < 120; i += 2 {
       if wilson(i, true) {
           fmt.Printf("%3d ", i)
           count++
           if count%20 == 0 {
               fmt.Println()
           }
       }
       if i == 2 {
           i--
       }
   }

}</lang>

Output:

 n prime
-- -----
 2 true
 3 true
 9 false
15 false
29 true
37 true
47 true
57 false
67 true
77 false
87 false
97 true
237 false
409 true
659 true

The first 120 prime numbers are:
  2   3   5   7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71 
 73  79  83  89  97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 
179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 
283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 
419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 
547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659