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