UVa 10533

From Algorithmist
Jump to navigation Jump to search

10533 - Digit Primes[edit]

Summary[edit]

A prime number that its sum of digits is also a prime number is consider as "digit prime". Count the number of "digit prime" numbers in a given range.

Explanation[edit]

Use Sieve of Eratosthenes and a simple DP.

Gotchas[edit]

  • Since there are quite a number of test inputs, (0<N<=500000), counting on demand will easily result in TLE.

Notes[edit]

  • Unlike some other problems, 1 is not treated as prime here in this problem.

Implementations[edit]

#include <stdio.h>
#include <string.h>

char sieve[500000];
int dpCount[1000000];

char isPrime(int n){
    if (n == 2)
        return 1;
    else if (! (n % 2))
        return 0;
    else {
        return sieve[(n-1)/2];
    }
}

int digitSum(int a){
    static char tempStr[10];
    static int len, sum;
    int i;

    sum = 0;
    sprintf(tempStr,"%d",a);
    len = strlen(tempStr);
    for (i = 0; i < len; i++){
        sum += (tempStr[i] - '0');
    }

    return sum;
}

void init(){
    int i, cur;
    memset(sieve,1,sizeof(sieve));
    memset(dpCount,0,sizeof(dpCount));

    /* sieve of eratosthenes */
    sieve[0] = 0;
    for (i = 3; i <= 1001; i+=2){
        if (sieve[(i-1)/2]){
            cur = 3*i;
            while (cur < 1000000){
                sieve[(cur-1)/2] = 0;
                cur = cur + i + i;
            }
        }
    }

    /* DP */
    dpCount[0] = 0;
    dpCount[1] = 0;
    dpCount[2] = 1;
    for (i = 3; i < 1000000; i++){
        if (isPrime(i) && isPrime( digitSum(i) )){
            dpCount[i] = dpCount[i-1] + 1;
        }
        else {
            dpCount[i] = dpCount[i-1];
        }
    }
}

int main(){
    int N, i, first, last;

    init();

    scanf("%d",&N);
    for (i = 0; i < N; i++){
        scanf("%d %d",&first,&last);
        printf("%d\n",dpCount[last]-dpCount[first-1]);
    }

    return 0;
}

Input[edit]

5
10 20
10 100
100 10000
1 999999
1 999998

Output[edit]

1
10
576
30123
30123

Solution[edit]