牛客练习赛129 A-数数

复习一下埃氏筛，快速拿出n以内质数。该题要是一个一个去计算“偶数”会超时非常多。

题意中”奇数“的本质是质数及质数的n次幂，所以先求出n以内所有质数及其n次幂的个数，就能计算出“偶数”的个数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 vector<bool> isPrime(5000005, true);
 4 vector <int> prime;
 5 int solve(int n) {
 6     if (n < 6) {
 7         return 0;
 8     }
 9     int oddCount = 0;
10     for(auto j : prime){
11         if (j > n){
12             break;
13         }
14         for (int i = 1;i < 23; ++i){ //题面数据n最大是5*10^5，在2^22到2^23之间，最大幂取22
15             if (pow(j, i) <= n){
16                 ++oddCount;
17             }else{
18                 break;
19             }
20         }
21     }
22     return n - oddCount - 1; //减去1，因为1非奇非偶
23 }
24 
25 int main() {
26     int n;
27     cin >> n;
28     //埃氏筛筛出质数
29     for (int i = 2; i <= sqrt(n); ++i) {
30         if (isPrime[i]) {
31             for (int j = i * i; j <= n; j += i) {
32                 isPrime[j] = false;
33             }
34         }
35     }
36     for (int i = 2;i <= n;++i){
37         if (isPrime[i])
38         prime.push_back(i);
39     }
40     cout<<solve(n);
41 }