n से छोटी सभी अभाज्य संख्याएं प्राप्त करने का एक दिलचस्प समाधान

यहां हम n से छोटी सभी अभाज्य संख्याओं को कुशल तरीके से उत्पन्न करना देखेंगे। इस दृष्टिकोण में हम विल्सन के प्रमेय का उपयोग करेंगे। उनके प्रमेय के अनुसार यदि कोई संख्या k अभाज्य है, तो ((k-1)! + 1) mod k 0 होगा। आइए इस विचार को प्राप्त करने के लिए एल्गोरिदम देखें।

यह विचार C या C++ जैसी भाषा में सीधे काम नहीं करेगा, क्योंकि यह बड़े पूर्णांकों का समर्थन नहीं करता। फैक्टोरियल बड़ी संख्याएं उत्पन्न करेगा।

एल्गोरिदम

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