 <p>This line:</p> <pre><code>A[j - 1] = 1; </code></pre> <p>Should be:</p> <pre><code>A[j] = 1; </code></pre> <p>So, now should works well:</p> <pre><code>#include&lt;stdio.h&gt; int A[1000000]; void sieve(int till) { for(int i = 2; i &lt; till; i++) { if(A[i] == 0) { for(int j = i*i; j &lt; till; j+=i) { A[j] = 1; } } } } int main() { int N,i; scanf("%i", &amp;N); for (i = 0;i &lt; N;i++) A[i] = 0; sieve(N); for (i = 2;i &lt; N;i++) if (A[i]) printf("%i is not prime\n",i); else printf("%i is prime\n",i); } </code></pre>