# UVa 10533

## Summary

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

Use Sieve of Eratosthenes and a simple DP.

## Gotchas

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

## Notes

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

## Implementations

```#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;
}
```

```5
10 20
10 100
100 10000
1 999999
1 999998
```

```1
10
576
30123
30123
```