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";

    }

}

Solution UVA: 10539 - Almost Prime Numbers

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10539 - Almost Prime Numbers	Accepted	C++11	0.000	0.000	183	1 mins ago

Suggest:

- Almost prime is the exponential of a prime number

- To find all the multipliers of prime numbers in the given time, we use the sieve prime

- After getting all the almost primes, to find out how many numbers are in a segment we use sort + binary search

#include<bits/stdc++.h>

#define int long long

using namespace std;

vector<int> a;

void sieve(int N) {

    int NN = N*N;

    bool isPrime[N+1];

    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 = 2; i <= N; ++i)

        if (isPrime[i])

            for(int j= i*i; j <= NN; j *= i) a.push_back(j);

}

int32_t main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    sieve(1000000);

    sort(a.begin(), a.end());

   

    int t;  cin >> t;

    while(t--){

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

        int L = lower_bound(a.begin(), a.end(), l) - a.begin();

        int R = lower_bound(a.begin(), a.end(), r) - a.begin();

        if (a[R] > r) R--;

        cout << R - L + 1 <<"\n";

    }

}