Generador de números primos en C++

1. Números primos
2. Genera números primos en C++
3. Utilice el método sqrt() para generar números primos en C++

Este rápido tutorial de programación guía la generación de todos los números primos dentro de un rango dado usando el método simple e intuitivo y un método eficiente de raíz cuadrada.

Números primos

Un número primo es un número divisible por uno o solo por sí mismo; por ejemplo, 17 es un número que solo es divisible por uno o por sí mismo. El único factor posible para un número primo P es P * 1.

Echemos un vistazo al conjunto de números primos:

Set of Prime Numbers = {2, 3, 5 , 7, 11, 13, 17, 23, .....,89, 97, .... }

En C++, podemos codificar tales escenarios y generar los números primos dentro de un rango e incluso verificar si un número es un número primo o no.

Genera números primos en C++

La lógica detrás de verificar si un número es primo es verificar su módulo con todos los números hasta la mitad de ese número. Si su módulo con cualquiera de los números es 0, entonces el número no es primo; de lo contrario, es primo.

Veamos el método más simple e intuitivo:

#include <iostream>
using namespace std;

int main() {
  int start = 0, end = 100, n;
  bool ifPrime = true;

  cout << "Prime numbers in between " << start << " and " << end
       << " are the following: " << endl;

  while (start < end) {
    ifPrime = true;

    if (start == 0 || start == 1) {
      ifPrime = false;
    }

    for (n = 2; n <= start / 2; ++n) {
      if (start % n == 0) {
        ifPrime = false;
        break;
      }
    }
    if (ifPrime) cout << start << ", ";

    ++start;
  }

  return 0;
}

Hemos tomado dos variables en el segmento de código anterior, inicio y fin. La variable “inicio” se inicializa en cero, y la variable “fin” se inicializa en 100 porque necesitamos números primos del 0 al 100.

Este rango se puede cambiar en cualquier momento o también se puede tomar como entrada del usuario.

Creamos un bucle desde el inicio hasta el final; en ese bucle, hicimos otro bucle for para comprobar si el número inicio es divisible por los números hasta la mitad de este número. Es porque, para un número no primo N, sólo pueden existir factores con los números a y b tales que a*b donde a<N/2 y b<N/2.

Por lo tanto, si el ciclo interno for permite que n se acerque a la mitad del valor inicio, el ciclo termina y el número se imprime en la línea 25 ya que ifprime sigue siendo true. Sin embargo, si cualquier valor de n divide correctamente el valor de inicio, la condición en la línea 19 se convierte en verdadera, configurando ifprime en false y finalizando el bucle for.

Producción:

Utilice el método sqrt() para generar números primos en C++

El método simple de cálculo de números primos discutido anteriormente era ineficiente ya que todavía requiere que dividamos hasta la mitad del número para verificar si es primo o no. Sin embargo, podemos aprovechar los hechos matemáticos para reducir la complejidad del tiempo de ejecución de nuestro programa.

El programa se ayuda del hecho de que para que un factor a*b sea igual a un número N, tanto a como b deben ser menores o iguales a la raíz cuadrada de N. Por ejemplo, para 36, los posibles pares de factores son (9*4), (18*2), (12*3), (6*6), por lo que cada par tiene a o b menor que la raíz cuadrada de 36.

Por tanto, para desaprobar que un número N no sea primo, sólo tenemos que comprobar si es divisible por algún número menor que la raíz cuadrada de N o no. Si no lo es, eso significa que el número es primo.

Ahora, codifiquemos el escenario:

#include <math.h>

#include <iostream>
using namespace std;

int main() {
  int start = 0, end = 100, n;
  bool ifPrime = true;

  cout << "Prime numbers in between " << start << " and " << end
       << " are the following: " << endl;

  while (start < end) {
    ifPrime = true;

    if (start == 0 || start == 1) {
      ifPrime = false;
    }

    for (n = 2; n <= sqrt(start); ++n) {
      if (start % n == 0) {
        ifPrime = false;
        break;
      }
    }
    if (ifPrime) cout << start << ", ";

    ++start;
  }

  return 0;
}

Hemos creado un bucle desde el inicio hasta el final, y en ese bucle sacaremos la raíz cuadrada del número, que será el número truncado del bucle interior.

Un ciclo interno verificará si el número actual es divisible por cualquier número hasta su raíz cuadrada. Si no, lo imprimimos como un número primo.

Producción: