G5017 [GESP202509 五级] 数字选取 题解

知识点：素数筛、数论性质、计数。

解题思路

统计1到n中的素数个数，再加上数字1，即为可选数量上限并可达到。

为什么正确

除1外每个被选数至少含一个质因子，两两互质要求这些因子不重复，最多选择素数数量个；选全部素数与1达到上界。

易错点

1也要选；不能把不同质数的幂当成额外名额，因为仍共用质因子。

复杂度

时间O(n log log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>p(n+1,1);
    p[0]=0;
    if(n>=1)p[1]=0;
    for(int i=2;i*i<=n;i++)if(p[i])for(int j=i*i;j<=n;j+=i)p[j]=0;
    cout<<accumulate(p.begin(),p.end(),1);
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。