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