Số nguyên tố Mersenne

197
Lập trình C++

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;
}