Solution UVA: 10533 - Digit Primes

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10533 - Digit Primes	Accepted	C++11	0.220	0.010	1261	55 secs ago

Suggest:

- Sieve Prime

- Involving DP 1D RSQ/RMQ

#include<bits/stdc++.h>

using namespace std;

int dp[1000111];

bool isPrime[1000111];

   

bool digit_prime(int n){

    int s= 0;

    while(n>0){

        s+=n%10;

        n/=10;

    }

    return isPrime[s];

}

void sieve(int N) {

    for(int i = 0; i <= N;++i) {

        isPrime[i] = true;

    }

    isPrime[0] = false;

    isPrime[1] = false;

    for(int i = 2; i * i <= N; ++i) {

         if(isPrime[i] == true) {

             // Mark all the multiples of i as composite numbers

             for(int j = i * i; j <= N; j += i)

                 isPrime[j] = false;

        }

    }

    for(int i=1; i<=N; i++)

        dp[i] = dp[i-1] + (digit_prime(i) && isPrime[i] ? 1 : 0);

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    sieve(1000000);

    int t;  cin >> t;

    while(t--){

        int l,r;    cin >> l >> r;

        cout<<dp[r] - dp[l-1]<<"\n";

    }

}