Số nguyên tố cân bằng (Balanced Prime) trong C++

Số nguyên tố cân bằng là số nguyên tố bằng trung bình cộng của số nguyên tố liền trước và liền sau nó. Công thức: Pₙ = (Pₙ₋₁ + Pₙ₊₁) / 2.

Các số nguyên tố cân bằng đầu tiên: 5, 53, 157, 173...

Bài toán: Cho n, tìm số nguyên tố cân bằng thứ n.

Ví dụ minh họa

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

int balancedPrimeNumber(int n) {
    bool prime[MAX + 1];
    memset(prime, true, sizeof(prime));
    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> v;
    for (int p = 3; p <= MAX; p += 2)
        if (prime[p]) v.push_back(p);
    
    int count = 0;
    for (int i = 1; i < v.size() - 1; i++) {
        if (v[i] == (v[i + 1] + v[i - 1]) / 2)
            count++;
        if (count == n)
            return v[i];
    }
    return -1;
}

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

Kết quả

157