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

    }

}