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

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

lautet:

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

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!