Programa C++ para verificar el número primo

Dado un número entero positivo, comprueba si el número es primo o no. Un primo es un número natural mayor que 1 que no tiene más divisores positivos que 1 y él mismo. Ejemplos de los primeros números primos son {2, 3, 5, Ejemplos:

Entrada:  n = 11
Salida: verdadero

Entrada:  n = 15
Salida: falso

Entrada:  n = 1
Salida: falso

// A school method based C++ program to check if a
// number is prime
#include <bits/stdc++.h>
using namespace std;
 
bool isPrime(int n)
{
    // Corner case
    if (n <= 1)
        return false;
 
    // Check from 2 to n-1
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            return false;
 
    return true;
}
 
// Driver Program to test above function
int main()
{
    isPrime(11) ? cout << " true\n" : cout << " false\n";
    isPrime(15) ? cout << " true\n" : cout << " false\n";
    return 0;
}

 true
 false

Complejidad temporal: O(n) 
Espacio auxiliar: O(1)
Método de escuela optimizado 

// A optimized school method based C++ program to check
// if a number is prime
#include <bits/stdc++.h>
using namespace std;
 
bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    // Using concept of prime number
    // can be represented in form of
    // (6*n + 1) or(6*n - 1) hence
    // we have to go for every multiple of 6 and
    // prime number would always be 1 less or 1 more than
    // the multiple of 6.
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Driver Program to test above function
int main()
{
    isPrime(4191) ? cout << " true\n" : cout << " false\n";
    isPrime(15) ? cout << " true\n" : cout << " false\n";
    return 0;
}

 false
 false

Consulte el artículo completo sobre Prueba de primalidad | ¡ Conjunto 1 (Introducción y Método Escolar) para más detalles!

Usando el teorema 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

Ejemplo : 

Input: p = 15
Output: Yes
(p-1)! = 14! = 87178291200 
87178291200 % 15  = 0

// 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()
{
  
   if(isPrime(4191) == true)
     cout << "True"<< endl;
   else
     cout << "false" << endl;
   
   if(isPrime(15) == true)
     cout << "True"<< endl;
   else
     cout << "false" << endl;
    return 0;
}
// this code is contributed by devendra solunke

false
false

Consulte el artículo completo sobre la implementación de la prueba de primalidad de Wilson para obtener más detalles.