(数论2.1.3)UVA 10533 Digit Primes(埃拉托斯特尼筛法)

 
/* 
 * UVA_10533.cpp 
 * 
 *  Created on: 2013年10月7日 
 *      Author: Administrator 
 */  
  
#include   
#include   
#include   
  
using namespace std;  
  
const int maxn = 1000001;  
bool u[maxn];  
int u2[maxn];  
  
void prepare() {  
    int i, j;  
    memset(u, true, sizeof(u));  
  
    for (i = 2; i <= maxn; ++i) {  
        if (u[i]) {  
            for (j = 2; j * i <= maxn; ++j) {  
                u[j * i] = false;  
            }  
        }  
    }  
  
}  
  
bool ok(int x) {  
  
    int k = 0;  
    while (x) {  
        k += x % 10;  
        x /= 10;  
    }  
  
    return u[k];  
}  
  
int main() {  
    prepare();  
    int t;  
    scanf("%d", &t);  
    int i, j;  
    for (i = 2; i <= maxn; ++i) {  
        if (u[i] && ok(i)) {  
            u2[i] = 1;  
        }  
    }  
  
    for (i = 2; i <= maxn; ++i) {  
        u2[i] += u2[i - 1];  
    }  
    while (t--) {  
        scanf("%d%d", &i, &j);  
        printf("%d\n", u2[j] - u2[i - 1]);  
    }  
  
    return 0;  
}