Heim > Artikel > Backend-Entwicklung > Eine interessante Lösung wäre, alle Primzahlen kleiner als n zu bekommen?
Hier erfahren Sie, wie Sie alle Primzahlen kleiner als n auf effiziente Weise generieren. Bei dieser Methode verwenden wir den Satz von Wilson. Nach seinem Satz gilt: Wenn eine Zahl k eine Primzahl ist, dann ist ((k - 1)! + 1) mod k 0. Schauen wir uns den Algorithmus an, um auf diese Idee zu kommen.
Diese Idee funktioniert in Sprachen wie C oder C++ nicht direkt, da sie keine großen Ganzzahlen unterstützt. Faktorial erzeugt große Zahlen. Die chinesische Übersetzung von
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
Das obige ist der detaillierte Inhalt vonEine interessante Lösung wäre, alle Primzahlen kleiner als n zu bekommen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!