Yogesh And Primes
Problem Statement
Suggest Edit
The first line of input contains one positive integer Q.
The following Q lines contains three spaced-separated integers A, B and K.
For each query, print the answer in a new line, if it exists, else print −1.
1≤Q≤100,000
1≤A≤B≤1,000,000
1≤K≤1,000,000
A≤P≤B
5
2 5 1
2 5 2
4 12 2
3 17 7
5 5 1
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;}
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.