Penyelesaian yang menarik ialah mendapatkan semua nombor perdana kurang daripada n?

Di sini kita akan melihat bagaimana untuk menjana semua nombor perdana kurang daripada n dengan cara yang cekap. Dalam kaedah ini kita akan menggunakan teorem Wilson. Menurut teoremnya, jika nombor k ialah nombor perdana, maka ((k - 1)! + 1) mod k akan menjadi 0. Mari lihat algoritma untuk mendapatkan idea ini.

Idea ini tidak akan berfungsi secara langsung dalam bahasa seperti C atau C++ kerana ia tidak menyokong integer yang besar. Faktorial menghasilkan jumlah yang besar. Terjemahan bahasa Cina bagi

algoritma

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

Contoh

ialah:

Contoh

#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

Atas ialah kandungan terperinci Penyelesaian yang menarik ialah mendapatkan semua nombor perdana kurang daripada n?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!