資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究C++ 中的梅森素數。
描述
在數學中，梅森素數是小於 2 的冪次的素數。也就是說，它是形式為 Mn = 2n − 1 的素數，其中 n 是某個整數。
編寫一個 C++ 程式來列印所有小於輸入正整數 n 的梅森素數。
產生梅森素數的指數 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
更新於： 2019 年 10 月 31 日
557 次瀏覽
廣告