Pierpont Prime ใน C++

ในปัญหานี้ เราได้รับตัวเลข n งานของเราคือพิมพ์ Pierpont prime numbers ทั้งหมดที่น้อยกว่า n

Pierpont Prime คือประเภทพิเศษของจำนวนเฉพาะที่มีรูปแบบ:

p = 2ⁱ . 3^k + 1

โดยที่ p เป็นจำนวนเฉพาะ และ i และ k เป็นจำนวนเต็มบางตัว

มาดูตัวอย่างเพื่อเข้าใจปัญหา:

Input - n = 50

Output - 2, 3, 5, 7, 13, 17, 19, 37

เพื่อแก้ปัญหานี้ เราต้องหาจำนวนเฉพาะทั้งหมดที่ตรงตามเงื่อนไข สำหรับสิ่งนี้ เราจะหาตัวเลขที่มีตัวประกอบเป็นกำลังของ 2 และ 3 และหาจำนวนเฉพาะทั้งหมด แล้วพิมพ์ตัวเลขที่เป็นทั้งจำนวนเฉพาะและตรงตามเงื่อนไข

ตัวอย่าง

โปรแกรมแสดงการนำโซลูชันของเราไปใช้งาน:

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

void printPierpontPrimes(int n) {
    bool arr[n+1];
    memset(arr, false, sizeof arr);
    int two = 1, three = 1;
    while (two + 1 < n) {
        arr[two] = true;
        while (two * three + 1 < n) {
            arr[three] = true;
            arr[two * three] = true;
            three *= 3;
        }
        three = 1;
        two *= 2;
    }
    vector<int> primes;
    for (int i = 0; i < n; i++)
        if (arr[i])
            primes.push_back(i + 1);
    memset(arr, false, sizeof arr);
    for (int p = 2; p * p < n; p++) {
        if (arr[p] == false)
            for (int i = p * 2; i < n; i += p)
                arr[i] = true;
    }
    for (int i = 0; i < primes.size(); i++)
        if (!arr[primes[i]])
            cout << primes[i] << "\t";
}

int main() {
    int n = 50;
    cout << "All Pierpont Prime Numbers less than " << n << " are :\n";
    printPierpontPrimes(n);
    return 0;
}

ผลลัพธ์

All Pierpont Prime Numbers less than 50 are : 2   3   5   7   13   17   19   37