Une solution intéressante serait d'obtenir que tous les nombres premiers soient inférieurs à n ?

Ici, nous verrons comment générer de manière efficace tous les nombres premiers inférieurs à n. Dans cette méthode, nous utiliserons le théorème de Wilson. D'après son théorème, si un nombre k est un nombre premier, alors ((k - 1)! + 1) mod k sera 0. Regardons l'algorithme pour avoir cette idée.

Cette idée ne fonctionnera pas directement dans des langages comme C ou C++ car elle ne prend pas en charge les grands entiers. Factorielle produit de grands nombres. La traduction chinoise de

algorithm

genAllPrime(n)

Begin
   fact := 1
   for i in range 2 to n-1, do
      fact := fact * (i - 1)
      if (fact + 1) mod i is 0, then
         print i
      end if
   done
End

Example

est :

Example

#include <iostream>
using namespace std;
void genAllPrimes(int n){
   int fact = 1;
   for(int i=2;i<n;i++){
      fact = fact * (i - 1);
      if ((fact + 1) % i == 0){
         cout<< i << " ";
      }
   }
}
int main() {
   int n = 10;
   genAllPrimes(n);
}

Output

2 3 5 7

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!