Prateek loves candy problem/

#1

i want to know that upto which value i iterate the sieve so that my solution is right ,i am getting tle in this code please help!

#include<bits/stdc++.h>
using namespace std;
vector sieve(int A) {
vectorpp;
for(int i=0;i<=A;i++)
{pp.push_back(1);}
pp[0]=0;
pp[1]=0;
for(int i=2;ii<=A;i++)
{
if(pp[i]==1)
{
for(int j=2;ij<=A;j++)
pp[j*i]=0;
}
}
vectoru;
for(int i=2;i<=A;i++)//https://www.interviewbit.com/problems/prime-numbers/#
{
if(pp[i]==1) u.push_back(i);
}return(u);
}

int main()
{
int n;
cin>>n;
while(n–)
{
int A;cin>>A;
vectorpp=sieve(10,000,000);

{cout<<pp[A-1]<<endl;}

}

return 0;
}

#2

Hi @amanm2292
The purpose of Sieve is to precompute.
Call the sieve function before running the testcase loop and store the sieve in your vector pp. You only need to do it one time. Then you can simply output pp[A-1] for the testcase loop. No need to compute Sieve again for every testcase.

1 Like
#3

i have call the sieve function only once to compute sieve .still i am getting run time error.
how can i know that upto which value of n the sieve upto that number is within 10^6?

#4

@amanm2292
It is mentioned in the question that answer can be as large as 10^6. So just make the sieve array of size 10^6. It would work just fine. For further code specific explanation , please share your code using ide.codingblocks.com so I can pinpoint the modifications and help you out.

1 Like
#5

thanks:hugs::relaxed:

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.