DP+埃氏筛法 Codeforces Round #304 (Div. 2) D. Soldier and Number Game

题目传送门

 /*
     题意：b+1，b+2，...，a 所有数的素数个数和
     DP+埃氏筛法：dp[i] 记录i的素数个数和，若i是素数，则为1；否则它可以从一个数乘以素数递推过来
                     最后改为i之前所有素数个数和，那么ans = dp[a] - dp[b]；
     详细解释：http://blog.****.net/catglory/article/details/45932593
 */
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <map>
 #include <cmath>
 using namespace std;

 typedef long long ll;

 const int MAXN = 5e6 + ;
 const int INF = 0x3f3f3f3f;
 int prime[MAXN];
 bool is_prime[MAXN];
 ll dp[MAXN];

 int seive(void)
 {
     for (int i=; i<=5e6; ++i)    is_prime[i] = true;
     is_prime[] = is_prime[] = false;
     int p = ;
     for (int i=; i<=5e6; ++i)
     {
         if (is_prime[i])
         {
             prime[++p] = i;
             for (int j=*i; j<=5e6; j+=i)    is_prime[j] = false;
         }
     }

     return p;
 }

 void solve(void)
 {
     int p = seive ();
     for (int i=; i<=5e6; ++i)
     {
         if (is_prime[i])    {dp[i] = ;    continue;}
         for (int j=; j<=p; ++j)
         {
             if (i % prime[j] == )
             {
                 dp[i] = dp[i/prime[j]] + ;    break;
             }
         }
     }

     for (int i=; i<=5e6; ++i)    dp[i] += dp[i-];
 }

 int main(void)        //Codeforces Round #304 (Div. 2) D. Soldier and Number Game
 {
     solve ();
     int t;    scanf ("%d", &t);
     while (t--)
     {
         int a, b;
         scanf ("%d%d", &a, &b);
         printf ("%I64d\n", dp[a] - dp[b]);
     }

     return ;
 }

 /*
 3
 3 1
 6 3
 5000000 4999995
 */