โปรแกรมตรวจสอบเลข Proth Number ใน C++

Proth Number คืออะไร?

Proth Number คือจำนวนเต็มบวกที่สามารถเขียนในรูปแบบ:

N = k × 2ⁿ + 1

โดยที่:

• k เป็นจำนวนเต็มบวกคี่ (odd positive integer)
• n เป็นจำนวนเต็มบวก (positive integer)
• k < 2ⁿ (เงื่อนไขเพิ่มเติมในนิยามบางรูปแบบ)

Proth Numbers แรกๆ

3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, ...

ตัวอย่างการแยกตัวประกอบ:

อัลกอริทึมการตรวจสอบ

1. ลบ 1 ออกจากตัวเลข: num = N - 1
2. หาตัวหารคี่ k ของ num โดยที่ k < num/k
3. ตรวจสอบว่า num/k เป็นกำลังของ 2 หรือไม่
4. ถ้าพบคู่ (k, n) ที่ตรงเงื่อนไข → เป็น Proth Number

ฟังก์ชันตรวจสอบกำลังของ 2

bool isPowerOfTwo(int num) {
    // ใช้ bitwise operation: n & (n-1) == 0 สำหรับกำลังของ 2
    return (num != 0) && ((num & (num - 1)) == 0);
}

ตัวอย่างโค้ด C++ สมบูรณ์

#include <iostream>
using namespace std;

bool isPowerOfTwo(int num) {
    return (num != 0) && ((num & (num - 1)) == 0);
}

bool isProth(int num) {
    // num = N - 1
    for (int k = 1; k < (num / k); k += 2) {  // k ต้องเป็นคี่
        if (num % k == 0) {
            int quotient = num / k;
            if (isPowerOfTwo(quotient)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    int testCases[] = {3, 5, 9, 13, 17, 18, 25, 33, 41, 49, 50, 65, 97, 100};
    int n = sizeof(testCases) / sizeof(testCases[0]);
    
    cout << "Proth Number Check:\n";
    for (int i = 0; i < n; i++) {
        int N = testCases[i];
        if (isProth(N - 1))
            cout << N << " is a Proth Number\n";
        else
            cout << N << " is not a Proth Number\n";
    }
    return 0;
}

ผลลัพธ์ตัวอย่าง

Proth Number Check:
3 is a Proth Number
5 is a Proth Number
9 is a Proth Number
13 is a Proth Number
17 is a Proth Number
18 is not a Proth Number
25 is a Proth Number
33 is a Proth Number
41 is a Proth Number
49 is a Proth Number
50 is not a Proth Number
65 is a Proth Number
97 is a Proth Number
100 is not a Proth Number

ความสำคัญของ Proth Numbers

• ใช้ในทฤษฎีจำนวน (Number Theory)
• เกี่ยวข้องกับ Proth Primes (Proth Number ที่เป็นจำนวนเฉพาะ)
• ใช้ในการทดสอบจำนวนเฉพาะขนาดใหญ่ (Proth's Theorem)
• มีการประยุกต์ในเข้ารหัสและคอมพิวเตอร์ควอนตัม

ความซับซ้อนของอัลกอริทึม

• เวลา: O(√N) - วนลูปหาตัวหารคี่สูงสุด √N
• พื้นที่: O(1)