Überprüfen Sie, ob eine Zahl in C++ eine Primzahl ist

1. Verwenden Sie die Trial Division-Methode, um zu überprüfen, ob eine Zahl in C++ eine Primzahl ist
2. Verwenden Sie die relativ optimierte Methode, um zu überprüfen, ob eine Zahl eine Primzahl ist

In diesem Artikel werden verschiedene Methoden zum Überprüfen, ob eine Zahl in C++ eine Primzahl ist, erläutert.

Verwenden Sie die Trial Division-Methode, um zu überprüfen, ob eine Zahl in C++ eine Primzahl ist

Der Primalitätstest ist der Name des Algorithmus, der bestimmt, ob die angegebene Zahl eine Primzahl ist. Die einfache Lösung, um zu überprüfen, ob eine Zahl eine Primzahl ist, besteht darin, die natürlichen Zahlen von der Eins zur angegebenen Zahl zu durchlaufen und zu prüfen, ob die Division keinen Rest hat.

Mehrere Erkenntnisse können diese Methode verbessern. Die erste - alle Teiler der Ganzzahl n sind kleiner oder gleich n/2, was bedeutet, dass der Suchraum reduziert wurde. Im folgenden Beispiel implementieren wir auch eine Funktion validateInput, um die Ganzzahl vom Benutzer zu übernehmen und zu überprüfen, ob sie erfolgreich in einer entsprechenden Variablen gespeichert wurde. Das Programm läuft in einer Endlosschleife, um den Benutzer kontinuierlich nach der Nummer zu fragen und die Nachricht dann in den Stream cout zu drucken.

#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);
}

Verwenden Sie die relativ optimierte Methode, um zu überprüfen, ob eine Zahl eine Primzahl ist

Wir können die vorherige Methode weiter optimieren, indem wir nur die Teiler testen, die kleiner oder gleich der Quadratwurzel aus dem n sind, was zufällig für alle natürlichen Zahlen gilt. Beachten Sie, dass alle Primzahlen größer als 3 als eine Form von 6k+-1 dargestellt werden können, wobei k eine ganze Zahl größer als Null ist. Dies impliziert ferner, dass die effiziente Methode zufällig die Teilbarkeit der Zahlen für die Werte von 2 und 3 testet. Wenn die vorherige Bedingung die angegebene Zahl nicht als Nicht-Primzahl beseitigt, sollten alle Zahlen der Form 6k+-1 getestet werden, die auch kleiner als die Quadratwurzel von n sind. Beachten Sie, dass validateInput aus der while-Schleife abbricht, wenn ein Terminal-Interrupt abgefangen wird (z. B. 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);
}