วิธีน่าสนใจหาจำนวนเฉพาะน้อยกว่า n ด้วยทฤษฎี Wilson ในภาษา C

Wilson's Theorem: k เป็นจำนวนเฉพาะ ⟺ (k-1)! ≡ -1 (mod k) ⟺ ((k-1)! + 1) % k == 0

ใช้หลักนี้หาจำนวนเฉพาะทั้งหมด < n โดยคำนวณ factorial แบบสะสม

ข้อจำกัด

Factorial โตเร็วมาก overflow เร็ว ไม่เหมาะกับ C/C++ สำหรับ n ใหญ่

โค้ดตัวอย่าง

#include <iostream>
using namespace std;

void genPrimes(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() {
    genPrimes(10);
    return 0;
}

ผลลัพธ์

2 3 5 7