➤ Problem Link : FRQPRIME
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int sieve[100001];
int arr[100001];
#define ll long long int
void initSieve(ll n)
{
memset(sieve,1,sizeof(sieve));
sieve[1]=0;
for(ll i=2;i<=sqrt(n);i++)
{
if(sieve[i])
{
for(ll j=i*i;j<=n;j+=i)
sieve[j]=0;
}
}
}
void setArr(ll n)
{
ll k=0;
for(ll i=1;i<=n;i++)
{
if(sieve[i])
arr[i]=++k;
else
arr[i]=k;
}
}
int main()
{
initSieve(100001);
setArr(100001);
ll t;
cin>>t;
while(t--)
{
ll n,k,temp,ans=0;
cin>>n>>k;
for(ll i=2;i<=n;i++)
{
// cout<<sieve[i]<<" ";
ll l;
if(sieve[i])
l=k+arr[i]-1;
else
l=k+arr[i];
temp=lower_bound(arr+i,arr+100001,l)-arr;
if(temp > n)
break;
// cout<<temp<<endl;
ans+=n-temp+1;
}
cout<<ans<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.