Maison > Article > développement back-end > 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
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
#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); }
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!