Initialize all entries of boolean array as true . A value in prime [ i ] will finally be false if i is Not a prime , else true
$ prime = array ( $ n + 1 ) ; for ( $ i = 0 ; $ i <= $ n ; $ i ++ ) $ prime [ $ i ] = true ; for ( $ p = 2 ; $ p * $ p <= $ n ; $ p ++ ) {