Prueba de primalidad | Conjunto 1 (Introducción y Método Escolar)

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
 

Método de la escuela: una solución simple es iterar a través de todos los números del 2 al n-1 y para cada número verificar si divide n. Si encontramos algún número que divide, devolvemos falso. 

A continuación se muestra la implementación de este método. 

C++

// 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; }

Java

// A school method based JAVA program // to check if a number is prime class GFG {       static boolean 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     public static void main(String args[])     {         if (isPrime(11))             System.out.println(" true");         else             System.out.println(" false");         if (isPrime(15))             System.out.println(" true");         else             System.out.println(" false");     } }   // This code is contributed // by Nikita Tiwari.

Python3

# A school method based Python3 # program to check if a number # is prime     def isPrime(n):       # Corner case     if n <= 1:         return False       # Check from 2 to n-1     for i in range(2, n):         if n % i == 0:             return False       return True     # Driver Program to test above function print("true") if isPrime(11) else print("false") print("true") if isPrime(14) else print("false")   # This code is contributed by Smitha Dinesh Semwal

C#

// A optimized school method based C# // program to check if a number is prime using System;   namespace prime { public class GFG {     public static bool isprime(int n)     {         // Corner cases         if (n <= 1)             return false;           for (int i = 2; i < n; i++)             if (n % i == 0)                 return false;           return true;     }       // Driver program     public static void Main()     {         if (isprime(11))             Console.WriteLine("true");         else             Console.WriteLine("false");           if (isprime(15))             Console.WriteLine("true");         else             Console.WriteLine("false");     } } }   // This code is contributed by Sam007

PHP

<?php // A school method based PHP // program to check if a number // is prime   function isPrime($n) {     // Corner case     if ($n <= 1) return false;       // Check from 2 to n-1     for ($i = 2; $i < $n; $i++)         if ($n % $i == 0)             return false;       return true; }   // Driver Code $tet = isPrime(11) ? " true\n" :                      " false\n"; echo $tet; $tet = isPrime(15) ? " true\n" :                      " false\n"; echo $tet;   // This code is contributed by m_kit ?>

JavaScript

<script>   // A school method based Javascript program to check if a // number is prime function isPrime(n) {     // Corner case     if (n <= 1) return false;       // Check from 2 to n-1     for (let i = 2; i < n; i++)         if (n % i == 0)             return false;     return true; }   // Driver Program to test above function     isPrime(11)? document.write(" true" + "<br>"): document.write(" false" + "<br>");     isPrime(15)? document.write(" true" + "<br>"): document.write(" false" + "<br>");   // This code is contributed by Mayank Tyagi   </script>

Producción

 true
 false

Complejidad temporal: O(n)
Espacio auxiliar: O(1)

Método de la escuela optimizada: podemos hacer las siguientes optimizaciones: en lugar de verificar hasta n, podemos verificar hasta √n porque un factor mayor de n debe ser un múltiplo de un factor menor que ya se haya verificado. La implementación de este método es la siguiente:

C++

// Optimised 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 square root of n     for (int i = 2; i <= sqrt(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; }   // This code is contributed by Vikash Sangai

Java

// Optimised school method based JAVA program // to check if a number is prime class GFG {       static boolean isPrime(int n)     {         // Corner case         if (n <= 1)             return false;           // Check from 2 to square root of n         for (int i = 2; i * i <= n; i++)             if (n % i == 0)                 return false;           return true;     }       // Driver Program     public static void main(String args[])     {         if (isPrime(11))             System.out.println(" true");         else             System.out.println(" false");         if (isPrime(15))             System.out.println(" true");         else             System.out.println(" false");     } }   // This code is contributed by Vikash Sangai

Python3

# Optimised school method based PYTHON program # to check if a number is prime # import the math module import math   # function to check weather the number is prime or not     def isPrime(n):       # Corner case     if (n <= 1):         return False       # Check from 2 to square root of n     for i in range(2, int(math.sqrt(n)) + 1):         if (n % i == 0):             return False     return True     # Driver Program to test above function print("true") if isPrime(11) else print("false") print("true") if isPrime(15) else print("false")   # This code is contributed by bhoomikavemula

C#

// Optimised school method based C# // program to check if a number is prime using System;   namespace prime { public class GFG {     public static bool isprime(int n)     {         // Corner cases         if (n <= 1)             return false;           for (int i = 2; i * i <= n; i++)             if (n % i == 0)                 return false;           return true;     }       // Driver program     public static void Main()     {         if (isprime(11))             Console.WriteLine("true");         else             Console.WriteLine("false");           if (isprime(15))             Console.WriteLine("true");         else             Console.WriteLine("false");     } } }   // This code is contributed by Vikash Sangai

JavaScript

<script>         // JavaScript code for the above approach     function isPrime(n)     {         // Corner case         if (n <= 1) return false;                // Check from 2 to square root of n         for (let i = 2; i*i <= n; i++)             if (n % i == 0)                 return false;                return true;     }           // Driver Code                   if(isPrime(11))             document.write(" true" + "<br/>");         else             document.write(" false" + "<br/>");         if(isPrime(15))             document.write(" true" + "<br/>");         else            document.write(" false" + "<br/>");   // This code is contributed by sanjoy_62.     </script>

Producción

 true
 false

Tiempo Complejidad: √n
Espacio Auxiliar: O(1)

Otro enfoque: se basa en el hecho de que todos los primos mayores que 3 son de la forma 6k ± 1, donde k es cualquier número entero mayor que 0. Esto se debe a que todos los números enteros se pueden expresar como (6k + i), donde i = −1, 0, 1, 2, 3 o 4. Y tenga en cuenta que 2 divide (6k + 0), (6k + 2) y (6k + 4) y 3 divide (6k + 3). Entonces, un método más eficiente es probar si n es divisible por 2 o por 3, luego verificar todos los números de la forma 6k ± 1 <= √n. Esto es 3 veces más rápido que probar todos los números hasta √n. (Fuente: wikipedia ).  

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to check the given number // is prime or not #include <bits/stdc++.h> using namespace std;   // Function to check if the given number // is prime or not. bool isPrime(int n) {     if (n == 2 || n == 3)         return true;       if (n <= 1 || n % 2 == 0 || n % 3 == 0)         return false;       // To check through all numbers of the form 6k ± 1     for (int i = 5; i * i <= n; i += 6) {         if (n % i == 0 || n % (i + 2) == 0)             return false;     }       return true; }   // Driver Code   int main() {     isPrime(11) ? cout << " true\n" : cout << " false\n";     isPrime(15) ? cout << " true\n" : cout << " false\n";     return 0; }

Java

// JAVA program to check the given number // is prime or not class GFG {     static boolean isPrime(int n)   {     // since 2 and 3 are prime     if (n == 2 || n == 3)       return true;       // if n<=1 or divided by 2 or 3 then it can not be prime     if (n <= 1 || n % 2 == 0 || n % 3 == 0)       return false;       // To check through all numbers of the form 6k ± 1     for (int i = 5; i * i <= n; i += 6)     {       if (n % i == 0 || n % (i + 2) == 0)         return false;     }       return true;   }     // Driver Program   public static void main(String args[])   {     if (isPrime(11))       System.out.println(" true");     else       System.out.println(" false");     if (isPrime(15))       System.out.println(" true");     else       System.out.println(" false");   } }   // This code is contributed by Ujjwal Kumar Bhardwaj

Python3

# Python program to check the given number # is prime or not   # Function to check if the given number # is prime or not. import math   def isPrime(n):     if n == 2 or n == 3:         return True     elif n <= 1 or n % 2 == 0 or n % 3 == 0:         return False                 # To check through all numbers of the form 6k ± 1     # until i <= square root of n, with step value 6     for i in range(5, int(math.sqrt(n))+1, 6):         if n % i == 0 or n % (i+2) == 0:             return False       return True   # # Driver code print(isPrime(11)) print(isPrime(20))   # # This code is contributed by Harsh Master

Producción

 true
 false

Tiempo Complejidad: √n
Espacio Auxiliar: O(1)