इस समस्या में, हमें एक पूर्णांक N दिया गया है और हमें N से कम या बराबर सभी प्रोथ अभाज्य संख्याओं को प्रिंट करना है।
प्रोथ अभाज्य संख्या
एक प्रोथ अभाज्य संख्या एक धनात्मक पूर्णांक है जिसका मान n = k * 2^n + 1 के रूप में दर्शाया जा सकता है। जहां k एक विषम धनात्मक पूर्णांक है और n एक धनात्मक पूर्णांक है और दोनों 2^n > k को संतुष्ट करते हैं।
उदाहरण - 3, 5, 13...
विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं -
इनपुट: N = 23 आउटपुट: 3, 5, 13, 17
इसके लिए, हम N से कम सभी अभाज्य संख्याएं ढूंढेंगे (इसके लिए हम एराटोस्थनीज की छलनी का उपयोग करेंगे)। और जांचेंगे कि प्रत्येक अभाज्य संख्या प्रोथ संख्या है या नहीं। और सभी प्रोथ संख्याओं को प्रिंट करें।
उदाहरण
#include <bits/stdc++.h> using namespace std; int prime[1000]; void SieveOfEratosthenes(int n){ for (int i = 1; i <= n + 1; i++) prime[i] = true; prime[1] = false; for (int p = 2; p * p <= n; p++) { if (prime[p] == true) { for (int i = p * p; i <= n; i += p) prime[i] = false; } } } bool isTwosExponent(int n){ return (n && !(n & (n - 1))); } bool isaProthNumber(int n){ int k = 1; while (k < (n / k)) { if (n % k == 0) { if (isTwosExponent(n / k)) return true; } k = k + 2; } return false; } bool isaProthPrime(int n){ if (isaProthNumber(n - 1)) { if(prime[n]) return true; else return false; } else return false; } int main(){ int n = 23; cout<<"Proth Prime Numbers less than or equal to "<<n<<" are :\n"; SieveOfEratosthenes(n); for (int i = 1; i <= n; i++) if (isaProthPrime(i)) cout<<i<<"\t"; return 0; } आउटपुट
23 से कम या बराबर प्रोथ अभाज्य संख्याएं हैं -
3 5 13 17
