Números primos – Part 3

• Un número primo es un número natural mayor que 1 , que solo es divisible por 1 y por sí mismo. Los primeros números primos son: 2 3 5 7 11 13 17 19 23 …..

Algunos datos interesantes sobre los números primos 

• Dos es el único número primo par.
• Cada número primo se puede representar en forma de 6n+1 o 6n-1 excepto el número primo 2 y 3, donde n es un número natural.
• Dos y tres son solo dos números naturales consecutivos que son primos.
• Conjetura de Goldbach: Todo número par mayor que 2 se puede expresar como la suma de dos números primos.
• Teorema de Wilson: 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

• Pequeño teorema de Fermat : si n es un número primo, entonces para cada a, 1 <= a < n,

an-1 ≡ 1 (mod n)
OR 
an-1 % n = 1

• Teorema de los números primos : La probabilidad de que un número n dado, elegido al azar, sea primo es inversamente proporcional a su número de dígitos, o al logaritmo de n.
• Conjetura de Lemoine : Cualquier entero impar mayor que 5 puede expresarse como la suma de un primo impar (todos los primos excepto 2 son impares) y un semiprimo par. Un número semiprimo es el producto de dos números primos. Esto se llama la conjetura de Lemoine.

¿Cómo comprobamos si un número es primo o no? 

Solución ingenua .  :
Una solución ingenua es iterar a través de todos los números desde 2 hasta sqrt (n) y para cada número verificar si divide n. Si encontramos algún número que divide, devolvemos falso.

// A school method based C++ program to
// check if a number is prime
#include <bits/stdc++.h>
using namespace std;
 
// function check whether a number
// is prime or not
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 Code
int main()
{
    isPrime(11) ? cout << " true\n" : cout << " false\n";
    return 0;
}

// A school method based Java program to
// check if a number is prime
import java.util.*;
import java.lang.*;
 
class GFG {
 
    // Check for number prime or not
    static boolean isPrime(int n)
    {
 
        // Check if number is less than
        // equal to 1
        if (n <= 1)
            return false;
 
        // Check if number is 2
        else if (n == 2)
            return true;
 
        // Check if n is a multiple of 2
        else if (n % 2 == 0)
            return false;
 
        // If not, then just check the odds
        for (int i = 3; i <= Math.sqrt(n); i += 2)
        {
            if (n % i == 0)
                return false;
        }
        return true;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        if (isPrime(19))
            System.out.println("true");
 
        else
            System.out.println("false");
    }
}
 
// This code is contributed by Ronak Bhensdadia

# A school method based Python3 program
# to check if a number is prime
 
# function check whether a number
# is prime or not
 
#import sqrt from math module
from math import sqrt
 
def isPrime(n):
 
    # Corner case
    if (n <= 1):
        return False
 
    # Check from 2 to sqrt(n)
    for i in range(2, int(sqrt(n))+1):
        if (n % i == 0):
            return False
 
    return True
 
 
# Driver Code
if isPrime(11):
    print("true")
else:
    print("false")
 
# This code is contributed by Sachin Bisht

// A school method based C# program to
// check if a number is prime
using System;
 
class GFG {
    // function check whether a
    // number is prime or not
    static bool isPrime(int n)
    {
        // Corner case
        if (n <= 1)
            return false;
 
        // Check from 2 to sqrt(n)
        for (int i = 2; i < Math.Sqrt(n); i++)
            if (n % i == 0)
                return false;
 
        return true;
    }
 
    // Driver Code
    static void Main()
    {
        if (isPrime(11))
            Console.Write(" true");
 
        else
            Console.Write(" false");
    }
}
 
// This code is contributed by Sam007

<?php
// A school method based PHP program to
// check if a number is prime
 
// function check whether a number
// is prime or not
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
if(isPrime(11))
    echo("true");
else
    echo("false");
 
// This code is contributed by Ajit.
?>

<script>
 
// A school method based Javascript program to
// check if a number is prime
 
  
// function check whether a number
// is prime or not
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 Code
 
    isPrime(11) ? document.write(" true" + "<br>") : document.write(" false" + "<br>");
 
// This code is contributed by Mayank Tyagi
 
</script>

 true

Complejidad del tiempo: O(sqrt(n)) , Espacio auxiliar y complejidad del espacio: O(1)

Enfoque más eficaz:

En el enfoque anterior, si el tamaño del número dado es demasiado grande, su raíz cuadrada también será muy grande, por lo que para manejar entradas de gran tamaño, trataremos con pocos números como 1, 2, 3 y los números que son divisibles por 2 y 3 en casos separados y para los números restantes iteraremos nuestro bucle de 5 a sqrt(n) y comprobaremos en cada iteración si esa (iteración) o (esa iteración+2) divide n o no. Si encontramos algún número que divide, devolvemos falso.

// A school method based C++ program to
// check if a number is prime
#include <bits/stdc++.h>
using namespace std;
 
// function check whether a number
// is prime or not
bool isPrime(int n)
{
    // Check if n=1 or n=0
    if (n <= 1)
        return false;
    // Check if n=2 or n=3
    if (n == 2 || n == 3)
        return true;
    // Check whether n is divisible by 2 or 3
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    // Check from 5 to square root of n
    // Iterate i by (i+6)
    for (int i = 5; i <= sqrt(n); i = 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";
    return 0;
}
//  This code is contributed by Suruchi kumari

// A school method based C program to
// check if a number is prime
#include <stdio.h>
#include<math.h>
// function check whether a number
// is prime or not
int isPrime(int n)
{
    // Check if n=1 or n=0
    if (n <= 1)
        return 0;
    // Check if n=2 or n=3
    if (n == 2 || n == 3)
        return 1;
    // Check whether n is divisible by 2 or 3
    if (n % 2 == 0 || n % 3 == 0)
        return 0;
    // Check from 5 to square root of n
    // Iterate i by (i+6)
    for (int i = 5; i <= sqrt(n); i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
 
    return 1;
}
 
// Driver Code
int main()
{
    if (isPrime(11) == 1)
        printf("true\n");
    else
       printf("false\n");
    return 0;
}
// This code is contributed by Suruchi Kumari

// Java program to check whether a number
class GFG
{
   
// Function check whether a number
// is prime or not
public static boolean isPrime(int n)
{
   if (n <= 1)
        return false;
   
    // Check if n=2 or n=3
    if (n == 2 || n == 3)
        return true;
   
    // Check whether n is divisible by 2 or 3
    if (n % 2 == 0 || n % 3 == 0)
        return false;
   
    // Check from 5 to square root of n
    // Iterate i by (i+6)
    for (int i = 5; i <= Math.sqrt(n); i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
  
    return true;    
    
}
 
// Driver Code  
public static void main(String[] args)
{
    if (isPrime(11))
    {
        System.out.println("true");
    }
    else
    {
        System.out.println("false");
    }
}
}
 
// This code is contributed by Sayan Chatterjee

Producción :

true

Complejidad del tiempo: O(sqrt(n))

Espacio auxiliar y complejidad del espacio : O(1)

Usando recursividad:

La recursividad también se puede usar para comprobar si un número entre 2 y n – 1 divide a n. Si encontramos algún número que divide, devolvemos falso.

// C++ program to check whether a number
// is prime or not using recursion
#include <iostream>
using namespace std;
 
// function check whether a number
// is prime or not
bool isPrime(int n)
{
    static int i = 2;
 
    // corner cases
    if (n == 0 || n == 1) {
        return false;
    }
 
    // Checking Prime
    if (n == i)
        return true;
 
    // base cases
    if (n % i == 0) {
        return false;
    }
    i++;
    return isPrime(n);
}
 
// Driver Code
int main()
{
 
    isPrime(35) ? cout << " true\n" : cout << " false\n";
    return 0;
}
 
// This code is contributed by yashbeersingh42

// Java program to check whether a number
// is prime or not using recursion
class GFG{
     
static int i = 2;
  
// Function check whether a number
// is prime or not
public static boolean isPrime(int n)
{
     
    // Corner cases
    if (n == 0 || n == 1)
    {
        return false;
    }
   
    // Checking Prime
    if (n == i)
        return true;
         
    // Base cases
    if (n % i == 0)
    {
        return false;
    }
    i++;
    return isPrime(n);
}
 
// Driver Code  
public static void main(String[] args)
{
    if (isPrime(35))
    {
        System.out.println("true");
    }
    else
    {
        System.out.println("false");
    }
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program to check whether a number
# is prime or not using recursion
 
# Function check whether a number
# is prime or not
def isPrime(n, i):
     
    # Corner cases
    if (n == 0 or n == 1):
        return False
     
    # Checking Prime 
    if (n == i):
        return True
     
    # Base cases
    if (n % i == 0):
        return False
     
    i += 1
     
    return isPrime(n, i)
 
# Driver Code
if (isPrime(35, 2)):
  print("true")
else:
  print("false")
   
#  This code is contributed by bunnyram19

// C# program to check whether a number
// is prime or not using recursion
using System;
class GFG {
     
    static int i = 2;
     
    // function check whether a number
    // is prime or not
    static bool isPrime(int n)
    {
      
        // corner cases
        if (n == 0 || n == 1) {
            return false;
        }
      
        // Checking Prime
        if (n == i)
            return true;
      
        // base cases
        if (n % i == 0) {
            return false;
        }
        i++;
        return isPrime(n);
    }
   
  static void Main() {
    if(isPrime(35))
    {
        Console.WriteLine("true");
    }
    else{
        Console.WriteLine("false");
    }
  }
}
 
// This code is contributed by divyesh072019

<script>
      // JavaScript program to check whether a number
      // is prime or not using recursion
 
      // function check whether a number
      // is prime or not
      function isPrime(n) {
        var i = 1;
 
        // corner cases
        if (n == 0 || n == 1) {
          return false;
        }
 
        // Checking Prime
        if (n == i) return true;
 
        // base cases
        if (n % i == 0) {
          return false;
        }
        i++;
        return isPrime(n);
      }
 
      // Driver Code
 
      isPrime(35) ? document.write(" true\n") : document.write(" false\n");
       
      // This code is contributed by rdtank.
    </script>

 false

Complejidad de tiempo: O(N) , Complejidad de espacio: O(N) 

• Soluciones eficientes 
  • Prueba de primalidad | Conjunto 1 (Introducción y Método Escolar)
  • Prueba de primalidad | Juego 2 (Método Fermat)
  • Prueba de primalidad | Conjunto 3 (Miller-Rabin)
  • Prueba de primalidad | Conjunto 4 (Solovay-Strassen)
  • Prueba de primalidad de Lucas

Algoritmos para encontrar todos los números primos menores que el N. 

• Tamiz de Eratóstenes
• Tamiz de Eratóstenes en complejidad de tiempo 0(n)
• Tamiz segmentado
• Tamiz de Sundaram
• Tamiz bit a bit
• ¡Artículos recientes sobre Sieve!

Más problemas relacionados con Número primo 

• Encuentra dos números primos distintos con un producto dado
• Imprimir todos los números primos menores o iguales a N
• Programa recursivo para números primos
• Encuentra dos números primos con una suma dada
• Encuentra el dígito más alto que aparece en números primos en un rango
• Factorización prima usando Sieve O (log n) para consultas múltiples
• Programa para imprimir todos los factores primos de un número dado
• Mínimo factor primo de números hasta n
• Factores primos de LCM de elementos de array – GeeksforGeeks
• Programa para la conjetura de Goldbach
• Números primos y Fibonacci
• Número compuesto
• ¡Artículos recientes sobre números primos!