Mô tả
Trong toán học, số nguyên tố Mersenne là số nguyên tố nhỏ hơn một lũy thừa của hai một đơn vị. Đó là, nó là số nguyên tố có dạng Mn = 2n - 1 với n là số nguyê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 n cho trước.
Các số mũ n cho ra số nguyên tố Mersenne là 2, 3, 5, 7,... và các số nguyên tố Mersenne kết quả là 3, 7, 31, 127.
Thuật toán
1. Sinh tất cả các số nguyên tố nhỏ hơn hoặc bằng số cho trước n 2. Duyệt qua tất cả các số dạng 2n-1 và kiểm tra xem chúng có phải số nguyên tố hay không
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; }
Kết quả
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