Initially all numbers are considered Primes .
$ sieve = array_fill ( 0 , $ N * 10 , true ) ; $ sieve [ 0 ] = $ sieve [ 1 ] = false ; for ( $ i = 2 ; $ i <= $ N * 10 ; $ i ++ ) { if ( $ sieve [ $ i ] ) { for ( $ j = $ i * $ i ; $ j <= $ N * 10 ; $ j += $ i ) { $ sieve [ $ j ] = false ; } } }