Compruebe si un número es primo en C++

1. Use el método de división de prueba para verificar si un número es primo en C++
2. Utilice un método relativamente optimizado para verificar si un número es primo

Este artículo explicará varios métodos para verificar si un número es primo en C++.

Use el método de división de prueba para verificar si un número es primo en C++

La prueba de primalidad es el nombre del algoritmo que determina si el número dado es un número primo. La solución simple para verificar si un número es primo sería iterar sobre los números naturales del uno al número dado y verificar si la división no tiene resto.

Varias ideas pueden mejorar este método. El primero: todos los divisores del entero n son menores o iguales que n/2, lo que significa que el espacio de búsqueda se ha reducido. En el siguiente ejemplo, también implementamos una función validateInput para tomar el número entero del usuario y verificar que se haya almacenado correctamente en una variable correspondiente. El programa se ejecuta en un bucle infinito para pedir continuamente al usuario el número y luego imprimir el mensaje en la secuencia cout.

#include <algorithm>
#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::numeric_limits;
using std::string;

bool isPrime(unsigned long long &n) {
  if (n <= 1) return false;

  for (uint i = 2; i < n; ++i)
    if (n % i == 0) return false;

  return true;
}

template <typename T>
T &validateInput(T &val) {
  while (true) {
    cout << "Enter the natural number: ";
    if (cin >> val) {
      break;
    } else {
      if (cin.eof()) exit(EXIT_SUCCESS);

      cout << "Enter a valid natural number!\n";
      cin.clear();
      cin.ignore(numeric_limits<std::streamsize>::max(), '\n');
    }
  }
  return val;
}

int main() {
  unsigned long long num;

  while (true) {
    validateInput(num);

    isPrime(num) ? cout << "Is Prime\n" : cout << "Is Not Prime\n";
  }

  exit(EXIT_SUCCESS);
}

Utilice un método relativamente optimizado para verificar si un número es primo

Podemos continuar optimizando el método anterior probando solo los divisores menores o iguales a la raíz cuadrada de la n, lo que resulta ser cierto para todos los números naturales. Tenga en cuenta que todos los números primos mayores que 3 se pueden representar como una forma de 6k+-1, donde k es un número entero mayor que cero. Además, implica que el método eficiente es probar la divisibilidad numérica para los valores de 2 y 3. Si la condición anterior no elimina el número dado como no primo, entonces todos los números de la forma 6k+-1 deben probarse que también sean menores que la raíz cuadrada de n. Tenga en cuenta que validateInput se rompe del bucle while cuando se detecta la interrupción del terminal (por ejemplo, Ctrl+D).

#include <algorithm>
#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::numeric_limits;
using std::string;

template <typename T>
T &validateInput(T &val) {
  while (true) {
    cout << "Enter the natural number: ";
    if (cin >> val) {
      break;
    } else {
      if (cin.eof()) exit(EXIT_SUCCESS);

      cout << "Enter a valid natural number!\n";
      cin.clear();
      cin.ignore(numeric_limits<std::streamsize>::max(), '\n');
    }
  }
  return val;
}

bool isPrime(unsigned long long &n) {
  if (n <= 3) return n > 1;

  if (n % 2 == 0 || n % 3 == 0) return false;

  for (int i = 5; i * i <= n; i += 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;

  return true;
}

int main() {
  unsigned long long num;

  while (true) {
    validateInput(num);

    isPrime(num) ? cout << "Is Prime\n" : cout << "Is Not Prime\n";
  }

  exit(EXIT_SUCCESS);
}