题解：SP3505 CPRIME - Prime Number Theorem

chenyuan3 · 2026-04-28 17:12:06 · 题解

题意：给定一个数 x，计算 \frac{|\pi(x)-\frac x{\ln x}|}{\pi(x)}\times100\%，其中 \pi(x) 是小于等于 x 的质数个数。多组数据。

先用筛法预处理出 1\sim10^8 中的质数，求前缀和即可得到 \pi(x)。然后直接计算即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxp = 1e7 + 10, maxn = 1e8 + 10;
ll p[maxp], cnt, pi[maxn];
void solve(ll n)
{
    cout << fabs(pi[n] - n / log(n)) / pi[n] * 100 << '\n';
}
int main()
{
    pi[0] = 1;
    pi[1] = 1;
    for (ll i = 2; i < maxn; i++)
    {
        if (!pi[i])
        {
            p[++cnt] = i;
        }
        for (ll j = 1; j <= cnt && i * p[j] < maxn; j++)
        {
            pi[i * p[j]] = 1;
            if (i % p[j] == 0)
            {
                break;
            }
        }
    }
    pi[0] = 0;
    for (ll i = 1; i < maxn; i++)
    {
        pi[i] = pi[i - 1] + !pi[i];
    }
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(1);
    ll n;
    while (cin >> n, n)
    {
        solve(n);
    }
    return 0;
}