C++のメルセンヌ素数。

説明

数学では、メルセンヌ素数は2の累乗より1少ない素数です。つまり、ある整数nに対してMn =2n −1の形式の素数です。

入力された正の整数nよりも小さいすべてのメルセンヌ素数を出力するC++プログラムを記述します。

メルセンヌ素数を与える指数nは2、3、5、7、...であり、結果のメルセンヌ素数は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