shank_punk's blog

By shank_punk, history, 7 years ago, In English

Hi guys. I tried implementing sieve today (I have done it 50+ times before), and my code was giving Runtime error :(

I tried to find out the error in my code but I don't know what is wrong.

#include<bits/stdc++.h> using namespace std; bool vis[1000002]; int main(){ int i,j; for(i=2;i<=100000;i++) vis[i]=true; for(i=2;i<=100000;i++){ if(!vis[i]) continue; for(j=i*i;j<=100000;j+=i){ vis[j]=false; } //cerr<<i<<" "; } return 0; }

If I change j+=i to j++, it does not show runtime error!(& the code will obviously be wrong & TLE)

UPDATE : Found my mistake(updated in comment section).

  • Vote: I like it
  • -1
  • Vote: I do not like it

7 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

UPDATE : I found out the error.

Its j = i*i. Since I declared i,j as int, 100000*100000 will cause overflow(don't know the exact technical term to be used). So I changed int to long long & it worked :)