二维rmq 离线 init O( n*n*logn*logn ) query O(1)
http://www.cnblogs.com/kuangbin/p/3227420.html
求1-n有多少个素数 n = 1e9
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace acm { 4 /// count primes between [1..n] (0< n <=1e9) 5 /// solution: dp 6 /// d(n, i) means that the number of value whose min prime number is bigger than i in [1..n] 7 /// d(n, i) = d(n, i-1) if number i is not a prime 8 /// d(n, i) = d(n, i-1) - d(n/i, i) + d(i, i-1) if number i is a prime 9 /// complex time: O(n^(3/4)), space: O(n^(1/2)) 10 struct CountPrime { 11 int solve(int n) { 12 if (n < 2) { 13 return 0; 14 } 15 dp[0] = 0; 16 int sqrtn = 1, length = 0; 17 for (; sqrtn <= n / sqrtn; ++sqrtn) { 18 dp[++length] = sqrtn - 1; 19 } 20 for (int i = sqrtn - 1; i > 0; --i) { 21 int val = n / i; 22 if (val != i) { 23 dp[++length] = val - 1; 24 } 25 } 26 for (int i = 1; i < sqrtn; ++i) { 27 if (dp[i] == dp[i-1]) { 28 continue; 29 } 30 for (int j=length; j>0; --j) { 31 int val = j < sqrtn ? j : n / (length - j + 1); 32 if (i > val / i) { 33 break; 34 } 35 int pre_statue_pos = val / i; 36 if (pre_statue_pos >= sqrtn) { 37 pre_statue_pos = length - n / pre_statue_pos + 1; 38 } 39 dp[j] += dp[i-1] - dp[pre_statue_pos]; 40 } 41 } 42 return dp[length]; 43 } 44 static const int maxn = 1e5+11; 45 int dp[maxn]; 46 }; 47 } // namespace acm 48 int main() 49 { 50 //freopen("dp.in", "r", stdin); 51 //freopen("dp.out", "w", stdout); 52 acm::CountPrime cp; 53 int n; 54 while (scanf ("%d", &n) != EOF) { 55 printf ("%d ", cp.solve(n)); 56 } 57 return 0; 58 }
end