HDU 4548 미소 수 (간단 한 문제 로 결 과 를 저장 할 때 시간 을 초과 하지 않도록 주의해 야 함)

미소 수
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 1149    Accepted Submission(s): 430
Problem Description
샤 오 밍 은 숫자 에 대한 연 구 를 비교적 좋아 하 는데 숫자 를 말 하 자마자 머 릿 속 에 많은 문제 가 떠 올 랐 다. 오늘 샤 오 밍 은 당신 이 소수 에 대한 인식 을 시험 해 보고 싶 어 한다.
문 제 는 다음 과 같다. 한 십 진수 가 소수 이 고 그 숫자 와 소수 라면 '미소 수' 라 고 부른다. 예 를 들 어 29 는 그 자체 가 소수 이 고 2 + 9 = 11 도 소수 이기 때문에 미소 수 이다.
한 구간 을 정 하면 이 구간 안에 몇 개의 미소 수가 있 는 지 계산 해 낼 수 있 습 니까?
 
Input
첫 번 째 줄 에 정수 T 를 입력 하면 모두 T 조 데이터 (T < = 10000) 가 있 음 을 나타 낸다.
다음은 총 T 줄 로 각 줄 에 두 개의 정수 L, R (1 & lt; = L & gt; = R & gt; = 1000000) 을 입력 하여 구간 의 왼쪽 값 과 오른쪽 값 을 나타 낸다.
 
Output
각 그룹의 데이터 에 대해 서 는 Case 수 를 먼저 출력 한 다음 구간 내 미소 수의 개수 (단점 값 L, R 포함) 를 출력 한다.
각 그룹의 데이터 가 한 줄 을 차지 하고 구체 적 인 출력 형식 은 샘플 을 참조 합 니 다.
 
Sample Input

   
   
   
   

    
    
    
    3
1 100
2 2
3 19
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    Case #1: 14
Case #2: 1
Case #3: 4
   
   
   
   

 
Source
2013 금 산 서 산 거 창의 게임 프로그램 챌 린 지 - 1 차 전 (2)
 
                 
 
제목 대의: 비교적 간단 하 니 바로 코드 를 올 려 라!주의해 야 할 것 은 먼저 소 수 를 선별 한 다음 에 미소 수 를 보존 할 때 유사 한 선분 수 와 같은 사상 을 이용 하여 특정한 단락 의 개 수 를 출력 해 야 한 다 는 것 이다.
           제목 주소: 미소 수
AC 코드:

#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
using namespace std;
int mark[1000005];
//int visi[1000005];
int ans[1000005];

int main()
{
    memset(mark,1,sizeof(mark));
    //memset(visi,0,sizeof(visi));
    ans[0]=0; ans[1]=0;
    int tes,cas,i,j,l,r;
    scanf("%d",&tes);
    for(i=2;i<=1000;i++)  //     
    {
        if(mark[i])
        {
            for(j=i*i;j<1000000;j+=i)
                mark[j]=0;
        }
    }

    for(i=2;i<1000000;i++)
    {
        if(mark[i])
        {
            int tmp=0;
            int x=i;
            while(x)
            {
                tmp+=x%10;
                x/=10;
            }
            if(mark[tmp])
            {
                //visi[i]=1;
                ans[i]=ans[i-1]+1;
            }
            else
                ans[i]=ans[i-1];
        }
        else
            ans[i]=ans[i-1];
    }

    for(cas=1;cas<=tes;cas++)
    {
        scanf("%d%d",&l,&r);
        //int res=0;
        //for(i=l;i<=r;i++)  //     TLE
           //res+=visi[i];
        printf("Case #%d: %d
",cas,ans[r]-ans[l-1]);
    }
    return 0;
}
//46MS 8052K