Time limit error in Prateek love candy

#1

https://ide.codingblocks.com/s/231787 why i am getting TLE for the test case 4.

#2

for(int i=3; i<1000000; i=i+2){
if(p[i]==1){
cnt++;
}
if(cnt==n){
cout<<i<<endl;
break;
}
}
in every query you are iterating till n (Reason for TLE)
which is not correct
if you have calculated all prime already then why not to store them in a vector and just print ans in O(1) by writing cout<<Prime[n]<<endl;

Modified code

#3

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.

#4

#include #include using namespace std; #define ll long long void primeSieve(ll int p){ p[2]=1; for(ll int i=3; i<1000000; i+=2){ p[i]=1; } for(ll int i=3; i<1000000; i=i+2){ if(p[i]){ for(ll int j=ii; j<1000000; j=j+2*i){ p[j]=0; } } } } void storePrime(vector v,ll int *p){ for(ll int i=0; i<1000000; i++){ if(p[i]){ v.push_back(i); } } } int main(){ int t; cin>>t; ll int p[1000000]={0}; primeSieve§; vectorv; storePrime(v,p); while(t–){ int n; cin>>n; cout<<v[n-1]<<endl; } }

#5

#include #include using namespace std; #define ll long long void primeSieve(ll int p){ p[2]=1; for(ll int i=3; i<1000000; i+=2){ p[i]=1; } for(ll int i=3; i<1000000; i=i+2){ if(p[i]){ for(ll int j=ii; j<1000000; j=j+2*i){ p[j]=0; } } } } void storePrime(vector v,ll int *p){ for(ll int i=0; i<1000000; i++){ if(p[i]){ v.push_back(i); } } } int main(){ int t; cin>>t; ll int p[1000000]={0}; primeSieve§; vectorv; storePrime(v,p); while(t–){ int n; cin>>n; cout<<v[n-1]<<endl; } } why am i getting segmentation fault in this code

#6

hello @itismohiton
pls save ur code in cb ide and share its link with me

#7


here is the link of code.

#8

ur array is taking too much memory,
a) use int for array

b) make it global

#9

it is still showing segmentation error. Can you please edit this code with comments?

#10

check now->

1 Like
#11

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.

#12

Hey aman, can you please tell me why i am getting segmentation error in this code?