Một giải pháp thú vị để nhận được tất cả các số nguyên tố nhỏ hơn n?

Ở đây chúng ta sẽ thấy cách tạo tất cả các số nguyên tố nhỏ hơn n một cách hiệu quả. Trong cách tiếp cận này, chúng ta sẽ sử dụng định lý Wilson. Theo định lý của ông nếu một số k là số nguyên tố thì ((k - 1)! + 1) mod k sẽ bằng 0. Hãy xem thuật toán để có được ý tưởng này.

Ý tưởng này sẽ không hoạt động trực tiếp trong ngôn ngữ C hoặc C ++ như ngôn ngữ vì nó sẽ không hỗ trợ các số nguyên lớn. Giai thừa sẽ tạo ra các số lớn.

Thuật toán

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

Ví dụ

#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);
}

Đầu ra

2 3 5 7