พิมพ์ Proth Primes ทั้งหมดจนถึง N ใน C++

ในปัญหานี้ เราจะได้รับจำนวนเต็ม N และต้องพิมพ์ Proth Prime Numbers ทั้งหมดที่น้อยกว่าหรือเท่ากับ N

Proth Prime Number

Proth Prime Number คือจำนวนเต็มบวกที่สามารถแสดงได้ในรูป n = k × 2ⁿ + 1 โดยที่ k เป็นจำนวนเต็มบวกคี่ และ n เป็นจำนวนเต็มบวก และทั้งสองต้องเป็นไปตามเงื่อนไข 2ⁿ > k

ตัวอย่าง - 3, 5, 13...

ตัวอย่างเพื่อความเข้าใจ

Input: N = 23
Output: 3, 5, 13, 17

สำหรับเรื่องนี้ เราจะหาจำนวนเฉพาะทั้งหมดที่น้อยกว่า N (โดยใช้ Sieve of Eratosthenes) และตรวจสอบว่าแต่ละจำนวนเฉพาะเป็น Proth Number หรือไม่ และพิมพ์ Proth Numbers ทั้งหมด

โปรแกรมตัวอย่าง

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

int prime[1000];

void SieveOfEratosthenes(int n) {
    for (int i = 1; i <= n + 1; i++)
        prime[i] = true;
    prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
}

bool isTwosExponent(int n) {
    return (n && !(n & (n - 1)));
}

bool isaProthNumber(int n) {
    int k = 1;
    while (k < (n / k)) {
        if (n % k == 0) {
            if (isTwosExponent(n / k))
                return true;
        }
        k = k + 2;
    }
    return false;
}

bool isaProthPrime(int n) {
    if (isaProthNumber(n - 1)) {
        if (prime[n])
            return true;
        else
            return false;
    }
    else
        return false;
}

int main() {
    int n = 23;
    cout << "Proth Prime Numbers less than or equal to " << n << " are :\n";
    SieveOfEratosthenes(n);
    for (int i = 1; i <= n; i++)
        if (isaProthPrime(i))
            cout << i << "\t";
    return 0;
}

ผลลัพธ์

Proth Prime Numbers less than or equal to 23 are -

3 5 13 17