सी ++ में मेर्सन प्राइम नंबर।

विवरण

गणित में, मेर्सन प्राइम एक अभाज्य संख्या है जो दो की शक्ति से एक कम है। अर्थात्, यह किसी पूर्णांक n के लिए Mn =2n - 1 के रूप की एक अभाज्य संख्या है।

इनपुट धनात्मक पूर्णांक n से छोटे सभी Mersenne Primes को प्रिंट करने के लिए एक C++ प्रोग्राम लिखें।

घातांक n जो Mersenne primes देते हैं वे 2, 3, 5, 7,... और परिणामी Mersenne primes 3, 7, 31, 127

एल्गोरिदम

1. Generate all the primes less than or equal to the given number n
2. Iterate through all numbers of the form 2n-1 and check if they are primes or not

उदाहरण

#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] == true) {
         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