इस समस्या में, हमें एक पूर्णांक N दिया जाता है और हमें सभी प्रोथप्राइम नंबर . को प्रिंट करना होता है N से कम या बराबर।
प्रोथ प्राइम नंबर
एक प्रोथ अभाज्य संख्या एक धनात्मक पूर्णांक है जिसका मान n =k * के रूप में दर्शाया जा सकता है 2 n + 1. जहां k एक विषम धनात्मक पूर्णांक है और n एक धनात्मक पूर्णांक है और दोनों 2 n को संतुष्ट करते हैं> के.
उदाहरण - 3, 5, 13…..
आइए विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं -
Input: N = 23 Output: 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