सभी अभाज्य संख्याओं को 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