เราจะมาดูวิธีการสร้างจำนวนเฉพาะทั้งหมดที่น้อยกว่า n อย่างมีประสิทธิภาพ ในแนวทางนี้ เราจะใช้ทฤษฎีบทของวิลสัน ตามทฤษฎีบทของเขาถ้าจำนวน k เป็นจำนวนเฉพาะ ดังนั้น ((k - 1)! + 1) mod k จะเป็น 0 ให้เราดูอัลกอริทึมเพื่อให้ได้แนวคิดนี้
แนวคิดนี้จะไม่ทำงานในภาษา C หรือ C++ โดยตรง เนื่องจากจะไม่รองรับจำนวนเต็มขนาดใหญ่ แฟคทอเรียลจะสร้างจำนวนมาก
อัลกอริทึม
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
ตัวอย่าง
#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);
} ผลลัพธ์
2 3 5 7
