Programa C++ para imprimir números primos del 1 al N

Dado un número N, la tarea es imprimir los números primos del 1 al N.

Ejemplos: 

Input: N = 10
Output: 2, 3, 5, 7

Input: N = 5
Output: 2, 3, 5 

Algoritmo:  

• Primero, tome el número N como entrada.
• Luego use un ciclo for para iterar los números de 1 a N
• Luego verifica que cada número sea un número primo. Si es un número primo, imprímelo.

Enfoque 1:  Ahora, según la definición formal, un número ‘n’ es primo si no es divisible por ningún otro número que no sea 1 y n. En otras palabras, un número es primo si no es divisible por ningún número del 2 al n-1.

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

// C++ program to display 
// Prime numbers till N
#include <bits/stdc++.h>
using namespace std;
  
// Function to check if a 
// given number is prime
bool isPrime(int n)
{
      // Since 0 and 1 is not 
      // prime return false.
      if(n == 1 || n == 0) return false;
    
      // Run a loop from 2 to n-1
      for(int i = 2; i < n; i++)
      {
        // if the number is divisible by i, 
        // then n is not a prime number.
        if(n % i == 0) return false;
      }
      // Otherwise n is a prime number.
      return true;
}
  
// Driver code
int main()
{
    int N = 100;
  
      // Check for every number from 1 to N
      for(int i = 1; i <= N; i++)
      {
          // Check if current number is prime
          if(isPrime(i)) 
          {
            cout << i << " ";
          }
    }
  
    return 0;
}

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 

Complejidad de tiempo: O(N^2), Complejidad de espacio: O(1)

Enfoque 2:  para verificar si un número es primo o no, ¿realmente necesitamos iterar a través de todos los números de 2 a n-1? Ya sabemos que un número ‘n’ no se puede dividir por ningún número mayor que ‘n/2’. Entonces, de acuerdo con esta lógica, solo necesitamos iterar a través de 2 a n/2 ya que un número mayor que n/2 no puede dividir n.

// C++ program to display 
// Prime numbers till N
#include <bits/stdc++.h>
using namespace std;
  
// Function to check if a given 
// number is prime
bool isPrime(int n)
{
    // Since 0 and 1 is not prime 
    // return false.
    if(n == 1 || n == 0) return false;
  
    // Run a loop from 2 to n/2.
    for(int i = 2; i <= n / 2; i++) 
    {
          // If the number is divisible by i, 
          // then n is not a prime number.
          if(n % i == 0) return false;
    }
    // Otherwise n is a prime number.
    return true;
}
  
// Driver code
int main()
{
    int N = 100;
  
      // Check for every number from 1 to N
      for(int i = 1; i <= N; i++)
      {
        // Check if current number is prime
        if(isPrime(i)) 
        {
          cout << i << " ";
        }
    }
  
    return 0;
}

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 

Complejidad de tiempo: O(N^2), Complejidad de espacio: O(1)

Método 3: si un número ‘n’ no se divide por ningún número menor o igual a la raíz cuadrada de n, entonces, no se dividirá por ningún otro número mayor que la raíz cuadrada de n. Entonces, solo necesitamos verificar hasta la raíz cuadrada de n.

// C++ program to display 
// Prime numbers till N
#include <bits/stdc++.h>
using namespace std;
  
// Function to check if a given 
// number is prime
bool isPrime(int n)
{
  // Since 0 and 1 is not prime 
  // return false.
  if(n == 1 || n == 0)return false;
    
  // Run a loop from 2 to 
  // square root of n.
  for(int i = 2; i * i <= n; i++)
  {
    // If the number is divisible by i, 
    // then n is not a prime number.
    if(n % i == 0)return false;
  }
  
  // Otherwise n is a prime number.
  return true;
}
  
// Driver code
int main()
{
    int N = 100;
  
      // Check for every number from 1 to N
      for(int i = 1; i <= N; i++)
      {
      // Check if current number is prime
      if(isPrime(i)) 
      {
        cout << i << " ";
      }
    }
  
    return 0;
}

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 

Complejidad de tiempo: O(N^(3/2)), Complejidad de espacio: O(1)

Puede optimizar aún más la complejidad del tiempo a O(n*log(log(n))).

Consulte el artículo completo sobre Programa para imprimir números primos del 1 al N. ¡para obtener más detalles!