Phương pháp Wilson tìm số nguyên tố < n trong C++

Định lý Wilson: k là nguyên tố ⟺ (k-1)! ≡ -1 (mod k) ⟺ ((k-1)! + 1) % k == 0.

Tính giai thừa lũy thừa: fact = 1; với i=2..n-1: fact *= (i-1); nếu (fact+1)%i==0 thì i là nguyên tố.

Lưu ý

Giai thừa tăng rất nhanh, tràn số nguyên. Chỉ dùng cho n nhỏ hoặc ngôn ngữ hỗ trợ big integer.

Chương trình

#include <iostream>
using namespace std;

void genPrimes(int n) {
    int fact = 1;
    for (int i = 2; i < n; i++) {
        fact *= (i - 1);
        if ((fact + 1) % i == 0)
            cout << i << " ";
    }
}

int main() {
    genPrimes(10); // 2 3 5 7
    return 0;
}

Kết quả

2 3 5 7