简答题
偏难
#20051
数字选取
数字选取


答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
int n, p[N], cnt, minp[N];
bool np[N], used[N];
int main() {
scanf("%d", &n);
// 欧拉筛,同时求最小质因子minp
for (int i = 2; i <= n; i++) {
if (!np[i]) {
p[++cnt] = i;
minp[i] = i;
}
for (int j = 1; j <= cnt && 1LL * i * p[j] <= n; j++) {
np[i * p[j]] = true;
minp[i * p[j]] = p[j];
if (i % p[j] == 0) break;
}
}
int k = n / 2;
int res = 0;
for (int i = k + 1; i <= n; i++) {
int prime = minp[i];
if (!used[prime]) {
used[prime] = true;
res++;
}
}
res += 1; // 选数字1
printf("%d\n", res);
return 0;
}</pre>
这道题暂未补解析。