Verifique se um número é Prime em C++

1. Use o método de divisão de teste para verificar se um número é o principal em C++
2. Use o método relativamente otimizado para verificar se um número é primo

Este artigo explicará vários métodos de como verificar se um número é primo em C++.

Use o método de divisão de teste para verificar se um número é o principal em C++

O teste de primalidade é o nome do algoritmo que determina se o número fornecido é um número primo. A solução simples para verificar se um número é primo seria iterar sobre os números naturais de um para o número fornecido e verificar se a divisão não tem resto.

Vários insights podem melhorar esse método. O primeiro - todos os divisores do inteiro n são menores ou iguais a n/2, o que significa que o espaço de busca foi reduzido. No exemplo a seguir, também implementamos uma função validateInput para obter o número inteiro do usuário e verificar se ele é armazenado com êxito em uma variável correspondente. O programa é executado em um loop infinito para pedir continuamente ao usuário o número e, em seguida, imprimir a mensagem no fluxo 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);
}

Use o método relativamente otimizado para verificar se um número é primo

Podemos continuar otimizando o método anterior testando apenas os divisores menores ou iguais à raiz quadrada do n, o que acontece ser verdadeiro para todos os números naturais. Observe que todos os primos maiores que 3 podem ser representados como uma forma de 6k+-1, onde k é um número inteiro maior que zero. Implica ainda que o método eficiente esteja testando a divisibilidade do número para os valores de 2 e 3. Se a condição anterior não elimina o número fornecido como não primo, então todos os números da forma 6k+-1 devem ser testados se também forem menores que a raiz quadrada de n. Observe que validateInput interrompe o loop while quando a interrupção do terminal é capturada (por exemplo, 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);
}