Chương trình kiểm tra số Proth trong C++

Cho một số 'n', nhiệm vụ là xác định xem số nguyên dương này có phải là số Proth hay không.

Số Proth là gì?

Số Proth có dạng:

$$N = k \cdot 2^n + 1$$

Trong đó, n là số nguyên dương và k là số nguyên lẻ dương.

Một số số Proth đầu tiên:

3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97...

Đầu vào 1

số: 17

Đầu ra 1

là số Proth

Đầu vào 2

số: 18

Đầu ra 2

không phải số Proth

Phương pháp tiếp cận

• Nhập số cần kiểm tra
• Áp dụng công thức: kiểm tra xem (num - 1) có thể viết dưới dạng k * 2^n với k lẻ
• Nếu thỏa mãn in "là số Proth", ngược lại in "không phải số Proth"

Thuật toán

Bước 1 → Hàm kiểm tra lũy thừa của 2:
bool laLuyThua2(int num) {
    return (num && !(num & (num - 1)));
}

Bước 2 → Hàm kiểm tra số Proth:
bool laSoProth(int num) {
    int k = 1;
    while (k < (num / k)) {
        if (num % k == 0) {
            if (laLuyThua2(num / k))
                return true;
        }
        k += 2; // k chỉ lấy giá trị lẻ
    }
    return false;
}

Bước 3 → Trong main():
int num = 17;
if (laSoProth(num - 1))
    cout << "là số Proth";
else
    cout << "không phải số Proth";

Ví dụ mã nguồn

#include <bits/stdc++.h>
using namespace std;

bool laLuyThua2(int num) {
    return (num && !(num & (num - 1)));
}

bool laSoProth(int num) {
    int k = 1;
    while (k < (num / k)) {
        if (num % k == 0) {
            if (laLuyThua2(num / k))
                return true;
        }
        k += 2;
    }
    return false;
}

int main() {
    int num = 17;
    if (laSoProth(num - 1))
        cout << "là số Proth";
    else
        cout << "không phải số Proth";
    return 0;
}

Kết quả chạy chương trình

là số Proth