Algorithm
Problem link- https://www.spoj.com/problems/NGIRL/
NGIRL - Namit In Trouble
Namit's girlfriend's birthday is coming next week. He went to a gift shop and saw N gifts are arranged in a single row in such a way that the position at which the gift is placed is equal to its price. (Position starts from 1.)
Namit's girlfriend being a maths student like those numbers which have exactly 3 divisors, so Namit decide to buy only those gifts which are placed at a position which have only 3 divisors, but Namit's girlfriend likes gifts whose price are above a certain amountK.
Now Namit wants to know total choices he have and how many gifts his girlfriend like for a given value of N.
Input
Input starts with 1<=T<=1000 (number of test cases). Then T lines follows each containing two integer 1<=N<10^10 (number of gifts at gift shop) and 1<=K<=10^10.
Output
You program should output two values indicating total number of choices and the number of gifts Namit's girlfriend likes.
Example
Input: 3 10 2 20 7 10 4 Output: 2 2 2 1 2 1
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h7gt;
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 1e6+5;
vector<ll> primes;
ll isPrime[MAXN];
vector<ll> primes_squares;
void sieve(){
isPrime[0] = isPrime[1] = 1;
for(int i = 2;i <= 1000000; i++){
if(isPrime[i] == 0){
primes.push_back(i);
if(i*1LL*i <= 1000000){
for(int j = i*i;j <= 1000000; j+=i)
isPrime[j] = 1;
}
}
}
}
void pre(){
for(auto i : primes){
primes_squares.push_back(i*1LL*i);
}
}
int main(){
io;
sieve();
pre();
int t;
cin >> t;
while(t--){
ll n, k;
cin >> n >> k;
// ans1 is numbers which have 3 divisors less than equal to n
if(n <= 3)
cout << 0 << " " << 0 << endl;
else{
ll ans1 = upper_bound(primes_squares.begin(), primes_squares.end(), n) - primes_squares.begin() - 1;
ans1+=1;
ll ans2 = upper_bound(primes_squares.begin(), primes_squares.end(), k) - primes_squares.begin() - 1;
ans2+=1;
cout << ans1 << " ";
if(ans1 >= ans2)
cout << (ans1-ans2) << endl;
else
cout << 0 << endl;
}
}
return 0;
}Input
10 2
20 7
10 4
Output
2 1
2 1
Demonstration
SPOJ Solution-Namit In Trouble-Solution in C, C++, Java, Python