Bài 21. Số P là số Mersenne nếu P nguyên tố và P = 2n – 1, mà n cũng là số nguyên tố.
a) Kiểm tra P có là số Mersenne hay không? Nếu có ghi ra 1 ngược lại ghi 0.
b) Tìm các số Mersenne nhỏ hơn hoặc bằng n.
c) Tìm các số Mersenne nằm trên đoạn [m, n].
Ví dụ:
|
MERSENNE.INP |
MERSENNE.OUT |
|
11 127 |
1 3 7 31 127 31 127 |
Code tham khảo:
#include <iostream>
#include <cmath>
using namespace std;
int nguyenTo(int n) {
if (n < 2) return 0;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) return 0;
}
return 1;
}
int Mersenne(int n){
int i = 0;
n += 1;
while (n > pow(2, i)) {
i++;
}
if (n == pow(2, i))
return 1;
else return 0;
}
int main() {
freopen("MERSENNE.INP","r",stdin);
freopen("MERSENNE.OUT","w",stdout);
int m, n;
cin >> m >> n;
if (nguyenTo(n) && Mersenne(n))
cout << 1 << endl;
else cout << 0 << endl;
for (int i = 2; i <= n; i++) {
if (nguyenTo(i) && Mersenne(i))
cout << i << " ";
}
cout << endl;
for (int i = m; i <= n; i++) {
if (nguyenTo(i) && Mersenne(i))
cout << i << " ";
}
return 0;
}