Vérifier si un nombre est premier en C++

1. Utilisez la méthode de la division d’essai pour vérifier si un nombre est premier en C++
2. Utilisez une méthode relativement optimisée pour vérifier si un nombre est premier

Cet article explique plusieurs méthodes pour vérifier si un nombre est premier en C++.

Utilisez la méthode de la division d’essai pour vérifier si un nombre est premier en C++

Le test de primalité est le nom de l’algorithme qui détermine si le nombre donné est un nombre premier. La solution simple pour vérifier si un nombre est premier serait d’itérer sur les nombres naturels de un au nombre donné et de vérifier si la division n’a pas de reste.

Plusieurs aperçus peuvent améliorer cette méthode. Le premier - tous les diviseurs de l’entier n sont inférieurs ou égaux à n/2, ce qui signifie que l’espace de recherche a été réduit. Dans l’exemple suivant, nous implémentons également une fonction validateInput pour prendre l’entier de l’utilisateur et vérifier qu’il est stocké avec succès dans une variable correspondante. Le programme s’exécute en boucle infinie pour demander continuellement le numéro à l’utilisateur puis imprimer le message dans le flux 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);
}

Utilisez une méthode relativement optimisée pour vérifier si un nombre est premier

Nous pouvons continuer à optimiser la méthode précédente en testant uniquement les diviseurs inférieurs ou égaux à la racine carrée du n, ce qui se trouve être vrai pour tous les nombres naturels. Notez que tous les nombres premiers supérieurs à 3 peuvent être représentés sous la forme 6k+-1, où k est un entier supérieur à zéro. Cela implique en outre que la méthode efficace consiste à tester la divisibilité des nombres pour les valeurs de 2 et 3. Si la condition précédente n’élimine pas le nombre donné comme non premier, alors tous les nombres de forme 6k+-1 doivent être testés qui sont également inférieurs à la racine carrée de n. Notez que validateInput sort de la boucle while lorsque l’interruption du terminal est interceptée (par exemple 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);
}