UVA 10533 - Digit Primes

Problem Link


Solution in c++

#include<bits/stdc++.h>

using namespace std;

/// Typedef
typedef long long ll;

#define sc1(a) scanf("%lld",&a)
#define sc2(a,b) scanf("%lld %lld",&a,&b)

#define pf1(a) printf("%lld\n", a)
#define pf2(a,b) printf("%lld %lld\n",a,b)

#define mx 1000000
#define mod 1000000007
#define PI acos(-1.0)
#define Accepted 0

#define size1 1000001

int drx[8] = {-2,-2,-1,-1,1,1,2,2};
int dcy[8] = {-1,1,-2,2,-2,2,-1,1};

int dirx[4] = { -1, 0, 1, 0 };
int diry[4] = { 0, -1, 0, 1 };


ll gcd(ll a,ll b){ if(b == 0) return a; return gcd(b, a % b); }
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}


bool check[size1];
vector <ll> prime;

void seive()
{
    memset(check, true, sizeof(check));

    for(ll i = 4; i < size1; i += 2) check[i] = false;

    check[0] = check[1] = false;

    for(ll i = 3; i * i < size1; i+=2){
        if(check[i]){
            for(ll j = i * i; j < size1; j += (2 * i)) check[j] = false;
        }
    }
}

ll sumOfDigits(ll num)
{
    ll ans = 0;

    while (num != 0){
        ans += num % 10;
        num /= 10;
    }

    return ans;
}

ll save[size1];

void cumulativeSum()
{
    save[0] = save[1] = 0;

    for(ll i = 2; i <= size1; i++){

        ll sum = 0;
        if(check[i])
            sum = sumOfDigits(i);

        if(check[sum]) save[i] = save[i - 1] + 1;
        else save[i] = save[i - 1];
    }
}

int main()
{
    seive();
    cumulativeSum();

    ll testCase;

    scanf("%lld", &testCase);
    while (testCase--) {

        ll first, last;
        scanf("%lld %lld", &first, &last);

        printf("%d\n", save[last] - save[first - 1]);
    }

    return Accepted;
}