विवरण
गणित में, मर्सेन अभाज्य संख्या (Mersenne prime) एक अभाज्य संख्या है जो दो की घात से एक कम होती है। अर्थात, यह कुछ पूर्णांक n के लिए Mₙ = 2ⁿ - 1 रूप की अभाज्य संख्या है।
एक C++ प्रोग्राम लिखें जो एक इनपुट धनात्मक पूर्णांक n से छोटे सभी मर्सेन अभाज्य संख्याओं को प्रिंट करे।
वे घातांक n जो मर्सेन अभाज्य देते हैं: 2, 3, 5, 7... और परिणामी मर्सेन अभाज्य हैं: 3, 7, 31, 127।
एल्गोरिदम
1. दी गई संख्या n से छोटे या बराबर सभी अभाज्य संख्याएं उत्पन्न करें 2. 2ⁿ-1 रूप की सभी संख्याओं पर पुनरावृति करें और जांचें कि वे अभाज्य हैं या नहीं
C++ उदाहरण
#include <iostream>
#include <algorithm>
using namespace std;
void generatePrimes(bool *primes, int n) {
fill(primes, primes + n + 1, true);
for (int p = 2; p * p <= n; ++p) {
if (primes[p]) {
for (int i = p * 2; i <= n; i += p)
primes[i] = false;
}
}
}
void mersennePrimes(int n) {
bool primes[n + 1];
generatePrimes(primes, n);
for (int i = 2; ((1 << i) - 1) <= n; ++i) {
int num = (1 << i) - 1;
if (primes[num]) cout << num << " ";
}
cout << endl;
}
int main() {
int n = 100;
cout << "Mersenne primes numbers till " << n << endl;
mersennePrimes(n);
return 0;
}
आउटपुट
Mersenne primes numbers till 100 3 7 31