একটি আকর্ষণীয় সমাধান n থেকে ছোট সব মৌলিক সংখ্যা পেতে?

এখানে আমরা দেখব কিভাবে কার্যকর উপায়ে 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