# Yogesh And Primes

Problem Statement
Suggest Edit

#### Note: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

##### Input Format :
``````The first line of input contains one positive integer Q.
The following Q lines contains three spaced-separated integers A, B and K.
``````
##### Output Format :
``````For each query, print the answer in a new line, if it exists, else print −1.
``````
##### Constraints:
``````1≤Q≤100,000
1≤A≤B≤1,000,000
1≤K≤1,000,000
A≤P≤B
``````
##### Sample Input :
``````5
2 5 1
2 5 2
4 12 2
3 17 7
5 5 1
``````
##### Sample Output :
``````2
3
7
-1
5``````
``#include <bits/stdc++.h>using namespace std;const int n=1e6+5;vector<int>prime(n,true);void sieve(){    for (int p = 2; p * p <= n; p++) {        if (prime[p] == true) {            for (int i = p * p; i <= n; i += p)                prime[i] = false;        }    }}int main(){    int q;cin>>q;      sieve();    vector<int>pre(n,0);    for(int i=2; i<=n; i++){        if(prime[i])pre[i]=pre[i-1]+1;        else pre[i]=pre[i-1];    }    while(q--){        int a,b,k;        cin>>a>>b>>k;        int ans=INT_MAX;        int low=a-1,high=b+1,mid;        while(low<high){            mid=(low+high)/2;            if(pre[mid]-pre[a-1]>=k){                ans=min(ans,mid);                high=mid;            }            else low=mid+1;        }        if(ans==INT_MAX || ans>b)ans=-1;        cout<<ans<<endl;                    }    return 0;}``