Pratik loves Candy

#1

https://hack.codingblocks.com/practice/p/339/52

My code is running fine for 10^4 but for 10^6 it gives run error.I have used sieve of eratosthenes

#include
using namespace std;
int main() {
int t;
cin>>t;
int p[1000001]={0};
p[1]=0;
p[0]=0;
p[2]=1;
for(int i=3;i<=1000000;i=i+2){
p[i]=1;
}

    for(int i=3;i<=1000000;i=i+2){
        if(p[i]){
            for(int j=i*i;j<=1000000;j=j+2*i){
                p[j]=0;
            }
        }
    }
 
   while(t>0){
   int n;
   cin>>n;
   int c=0;
   int o=0;
   for(int i=0;c<n;i++){
       if(p[i]){
       c++;
       o=i;}
   }
   cout<<o<<endl;
   t--;
}
return 0;

}

#2

Its beacuse of your
for(int j=i * i;j<=100000;j++) loop
Here your i * i goes out of int bounds and a overflow occurs. Try taking both i and j as long long int and it should work fine.

Also declare array globally, as if you declare array in main() function it goes into stack, while if you
declare it globally it goes in heap.

Hope it helps

1 Like