จำนวนเฉพาะสมดุล (Balanced Prime) ใน C++

จำนวนเฉพาะสมดุล คืออะไร?

จำนวนเฉพาะที่มีความต่างกับจำนวนเฉพาะก่อนหน้าและถัดไปเท่ากัน คือค่าเฉลี่ยของจำนวนเฉพาะสองข้าง

สูตร: Pₙ = (Pₙ₋₁ + Pₙ₊₁) / 2

จำนวนเฉพาะ: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, ...

จำนวนเฉพาะสมดุลตัวแรกๆ: 5, 53, 157, 173, ...

5 = (3+7)/2 ✓
53 = (47+59)/2 ✓
157 = (151+163)/2 ✓

ปัญหา

หาจำนวนเฉพาะสมดุลตัวที่ n

วิธีแก้ปัญหา

ใช้ Sieve of Eratosthenes หาจำนวนเฉพาะทั้งหมด
เก็บจำนวนเฉพาะในเวกเตอร์
ตรวจสอบแต่ละจำนวนเฉพาะ (ยกเว้นตัวแรกและตัวสุดท้าย) ว่าเป็นสมดุลหรือไม่
นับจนครบ n ตัว

ตัวอย่างโค้ด C++

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

const int MAX = 10000; // เพิ่มขอบเขตเพื่อหา balanced prime มากขึ้น

int balancedPrimeNumber(int n) {
    vector<bool> prime(MAX + 1, true);
    prime[0] = prime[1] = false;
    
    for (int p = 2; p * p <= MAX; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= MAX; i += p)
                prime[i] = false;
        }
    }
    
    vector<int> primes;
    for (int p = 2; p <= MAX; p++)
        if (prime[p]) primes.push_back(p);
    
    int count = 0;
    for (int i = 1; i + 1 < primes.size(); i++) {
        if (primes[i] == (primes[i-1] + primes[i+1]) / 2) {
            count++;
            if (count == n)
                return primes[i];
        }
    }
    return -1; // ไม่พบในขอบเขต MAX
}

int main() {
    int n = 3;
    cout << "Balanced prime #" << n << " = " << balancedPrimeNumber(n) << endl;
    return 0;
}

ผลลัพธ์

Balanced prime #3 = 157