ACM 10533 - Digit Primes

#include <stdio.h>

#define MAXLEN 1000000
int prime[55] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 
                 0, 1, 0, 1, 0, 0, 0, 1, 0, 1,
                 0, 0, 0, 1, 0, 0, 0, 0, 0, 1,
                 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 
                 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 
                 0, 0, 0, 1, 0};
int digitPrime[MAXLEN] = {0};

int makeprime(){
    int i, j, sum, n, s = 0;
    for(i = 2;i < MAXLEN; i ++)
    {  
        if(!digitPrime[i])
        {
            for(j = i + i; j < MAXLEN; j += i)
                digitPrime[j] = 1;
            sum = 0;
            n = i;
            while (n)
                sum += n % 10, n = n / 10;
            if (prime[sum])
            { ++ s; digitPrime[i] = s; }
            else digitPrime[i] = s;    
        }
        else digitPrime[i] = s;
    }
}

int main()
{
    makeprime();
    int n, t1, t2, i, count;
    scanf("%d", &n);
    while (n --)
    {
        count = 0;  
        scanf("%d %d", &t1, &t2);
        printf("%d\n", digitPrime[t2] - digitPrime[t1] + (digitPrime[t1] != digitPrime[t1 - 1]));
    }
    return 0;
}

回目錄
回首頁