Mark all multiples of squares as non - prime
for ( $ r = 5 ; $ r * $ r < $ limit ; $ r ++ ) { if ( $ sieve [ $ r ] ) { for ( $ i = $ r * $ r ; $ i < $ limit ; $ i += $ r * $ r ) $ sieve [ $ i ] = false ; } }