বিবরণ
গণিতে, মেরসেন প্রাইম (Mersenne prime) হল এমন একটি প্রাইম সংখ্যা যা দুইর ঘাত থেকে এক কম। অর্থাৎ, এটি Mn = 2ⁿ - 1 আকারের প্রাইম সংখ্যা কিছু পূর্ণসংখ্যা n-এর জন্য।
একটি C++ প্রোগ্রাম লিখুন যা একটি ইনপুট ধনাত্মক পূর্ণসংখ্যা n-র চেয়ে ছোট সব মেরসেন প্রাইম প্রিন্ট করবে।
যে এক্সপোনেন্ট n-গুলো মেরসেন প্রাইম দেয় সেগুলো হল ২, ৩, ৫, ৭... এবং ফলাফলে মেরসেন প্রাইম হচ্ছে ৩, ৭, ৩১, ১২৭।
এলগরিদম
1. দেওয়া সংখ্যা n পর্যন্ত সব প্রাইম জেনারেট করুন 2. 2ⁿ-1 আকারের সব সংখ্যা ওপর ইটারেট করুন এবং চেক করুন সেগুলো প্রাইম কিনা
উদাহরণ কোড
#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
