Implementación de la prueba de primalidad de Wilson

Dado un número N, la tarea es verificar si es primo o no usando la prueba de primalidad de Wilson . Imprime ‘1’ si el número es primo, de lo contrario imprime ‘0’.
El teorema de Wilson establece que un número natural p > 1 es un número primo si y solo si

    (p - 1) ! ≡  -1   mod p 
OR  (p - 1) ! ≡  (p-1) mod p

Ejemplos: 

Input: p = 5
Output: Yes
(p - 1)! = 24
24 % 5  = 4

Input: p = 7
Output: Yes
(p-1)! = 6! = 720
720 % 7  = 6

A continuación se muestra la implementación de la prueba de primalidad de Wilson  

// C++ implementation to check if a number is
// prime or not using Wilson Primality Test
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the factorial
long fact(const int& p)
{
    if (p <= 1)
        return 1;
    return p * fact(p - 1);
}
 
// Function to check if the
// number is prime or not
bool isPrime(const int& p)
{
    if (p == 4)
        return false;
    return bool(fact(p >> 1) % p);
}
 
// Driver code
int main()
{
    cout << isPrime(127);
    return 0;
}

// Java implementation to check if a number is 
// prime or not using Wilson Primality Test
public class Main
{
    // Function to calculate the factorial
    public static long fact(int p)
    {
        if (p <= 1)
            return 1;
        return p * fact(p - 1);
    }
       
    // Function to check if the
    // number is prime or not
    public static long isPrime(int p)
    {
        if (p == 4)
            return 0;
        return (fact(p >> 1) % p);
    }
 
    public static void main(String[] args) {
        if(isPrime(127) == 0)
        {
            System.out.println(0);
        }
        else{
            System.out.println(1);
        }
    }
}
 
// This code is contributed by divyesh072019

# Python3 implementation to check if a number is
# prime or not using Wilson Primality Test
 
# Function to calculate the factorial
def fact(p):
     
    if (p <= 1):
        return 1
 
    return p * fact(p - 1)
 
# Function to check if the
# number is prime or not
def isPrime(p):
     
    if (p == 4):
        return 0
         
    return (fact(p >> 1) % p)
 
# Driver code
if (isPrime(127) == 0):
    print(0)
else:
    print(1)
 
# This code is contributed by rag2127

// C# implementation to check if a number is 
// prime or not using Wilson Primality Test
using System;
class GFG {
     
    // Function to calculate the factorial
    static long fact(int p)
    {
        if (p <= 1)
            return 1;
        return p * fact(p - 1);
    }
        
    // Function to check if the
    // number is prime or not
    static long isPrime(int p)
    {
        if (p == 4)
            return 0;
        return (fact(p >> 1) % p);
    }
     
  static void Main() {
    if(isPrime(127) == 0)
    {
        Console.WriteLine(0);
    }
    else{
        Console.WriteLine(1);
    }
  }
}
 
// This code is contributed by divyeshrabadiya07

<script>
    // Javascript implementation to check if a number is
    // prime or not using Wilson Primality Test
     
    // Function to calculate the factorial
    function fact(p)
    {
        if (p <= 1)
            return 1;
        return p * fact(p - 1);
    }
 
    // Function to check if the
    // number is prime or not
    function isPrime(p)
    {
        if (p == 4)
            return false;
             
          if(fact(p >> 1) % p == 0)
        {
            return 0;
        }
         
        return 1;
    }
     
    document.write(isPrime(127));
     
    // This code is contributed by suresh07.
</script>

1

¿Como funciona? 

1. Podemos verificar rápidamente el resultado de p = 2 o p = 3.
2. Para p > 3: Si p es compuesto, entonces sus divisores positivos están entre los enteros 1, 2, 3, 4, … , p-1 y es claro que mcd((p-1)!,p) > 1 , entonces no podemos tener (p-1)! = -1 (mod p).
3. Ahora veamos cómo es exactamente -1 cuando p es un número primo. Si p es primo, entonces todos los números en [1, p-1] son ​​primos relativos a p. Y para cada número x en el rango [2, p-2], debe existir un par y tal que (x*y)%p = 1. Entonces

    [1 * 2 * 3 * ... (p-1)]%p 
 =  [1 * 1 * 1 ... (p-1)] // Group all x and y in [2..p-2] 
                          // such that (x*y)%p = 1
 = (p-1)

Complejidad del tiempo: O(N) como función factorial recursiva toma la complejidad de O(n) 

Complejidad espacial : O(N)