hdu 4548素数メーター

リンク:http://acm.hdu.edu.cn/showproblem.php?pid=4548 方法:ふるいは表を打って、更に素数の中で美素数かどうかを判断します.比較的に裸です.でも最初はこのようにすると時間が超過します.一つの配列を使って現在の数字に保存すると、もういくつかのアメリカ素数が現れています.最後に区間の両端に対応するものを減らしてもいいです.

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define M 1000001
bool is_prime[M]; //   
bool is[M]; //    
int dp[M];
bool judge(char ss[])
{
    int sum = 0;
    for(int i = 0;i < strlen(ss);i++)
    {
        sum += ss[i]-'0';
    }
    return is_prime[sum];
}
int main()
{
    fill(is_prime,is_prime+M,true);
    for(int i = 2;i <= M;i++)  //    
    {
        if(is_prime[i])
        {
            for(int j = 2*i;j <= M;j += i)
                is_prime[j] = false;
        }
    }
    is_prime[1] = false;
    for(int i = 1;i <= M;i++)
    {
        char s[100];
        sprintf(s,"%d",i);
        if(is_prime[i] && judge(s))
            is[i] = true;
    }
    fill(dp,dp+M,0);
    for(int i = 1;i <= M;i++)  //    dp[i]    i          (  i)
    {
        if(is[i])
            dp[i] = dp[i-1]+1;
        else dp[i] = dp[i-1];
    }
    int t;
    while(scanf("%d",&t)==1)
    {
        for(int i = 1;i <= t;i++)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            int ans;
            if(!is[a])
                ans = dp[b]-dp[a];
            else ans = dp[b]-dp[a]+1;
            printf("Case #%d: %d
",i,ans); //       dp[b]-dp[a-1]     a       ，          a  
        }
    }
    return 0;
}