Số nguyên tố Mersenne trong C ++.

Mô tả

Trong toán học, một số nguyên tố Mersenne là một số nguyên tố nhỏ hơn một lũy thừa của hai. Nghĩa là, nó là một số nguyên tố có dạng Mn =2n - 1 với một số nguyên n.

Viết chương trình C ++ để in tất cả các Số nguyên tố Mersenne nhỏ hơn một số nguyên dương đầu vào n.

Số mũ n tạo ra các số nguyên tố Mersenne là 2, 3, 5, 7, ... và các số nguyên tố Mersenne thu được là 3, 7, 31, 127

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Mersenne primes numbers till 100
3 7 31