Controlla se un numero è primo in C++

1. Utilizzare il metodo di divisione di prova per verificare se un numero è primo in C++
2. Utilizzare un metodo relativamente ottimizzato per verificare se un numero è primo

Questo articolo spiegherà diversi metodi per verificare se un numero è primo in C++.

Utilizzare il metodo di divisione di prova per verificare se un numero è primo in C++

Il test di primalità è il nome dell’algoritmo che determina se il numero dato è un numero primo. La soluzione semplice per verificare se un numero è primo sarebbe iterare sui numeri naturali da uno al numero dato e controllare se la divisione non ha resto.

Diverse informazioni possono migliorare questo metodo. Il primo - tutti i divisori dell’intero n sono minori o uguali a n/2, il che significa che lo spazio di ricerca è stato ridotto. Nell’esempio seguente, implementiamo anche una funzione validateInput per prendere il numero intero dall’utente e verificare che sia memorizzato correttamente in una variabile corrispondente. Il programma viene eseguito in un bucle infinito per chiedere continuamente all’utente il numero e quindi stampare il messaggio nel flusso 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);
}

Utilizzare un metodo relativamente ottimizzato per verificare se un numero è primo

Possiamo continuare a ottimizzare il metodo precedente testando solo i divisori minori o uguali alla radice quadrata dalla n, che risulta essere vero per tutti i numeri naturali. Nota che tutti i numeri primi maggiori di 3 possono essere rappresentati come una forma di 6k+-1, dove k è un numero intero maggiore di zero. Implica inoltre che il metodo efficiente stia testando la divisibilità del numero per i valori di 2 e 3. Se la condizione precedente non elimina il numero dato come non primo, devono essere verificati tutti i numeri di forma 6k+-1 che sono anche inferiori alla radice quadrata di n. Notare che validateInput si interrompe dal cicli while quando viene rilevato l’interruzione del terminale (ad esempio 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);
}