এখানে আমরা দেখব কিভাবে n-র চেয়ে ছোট সব প্রাইম নাম্বার দক্ষতার সাথে জেনারেট করা যায়। এই পদ্ধতিতে উইলসনের থিওরেম (Wilson's theorem) ব্যবহার করা হয়। তার থিওরেম অনুযায়ী, যদি একটি সংখ্যা k প্রাইম হয়, তবে ((k - 1)! + 1) mod k = 0 হবে। এই আইডিয়ার অ্যালগরিদম নিচে দেওয়া হলো।
এই আইডিয়া সরাসরি সি বা সি++-এ কাজ করবে না, কারণ বড় ইন্টিজার সাপোর্ট করে না। ফ্যাক্টোরিয়াল খুব বড় সংখ্যা জেনারেট করে।
অ্যালগরিদম
genAllPrime(n)
শুরু
fact := 1
i = 2 থেকে n-1 পর্যন্ত লুপ চালাও
fact := fact * (i - 1)
যদি (fact + 1) mod i == 0 হয়, তবে
i প্রিন্ট করো
শেষ যদি
লুপ শেষ
শেষ
উদাহরণ কোড
#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);
return 0;
}
আউটপুট
2 3 5 7
