Loop to mark the prime numbers upto the Square root of N
for ( int i = 2 ; i <= ( int ) Math . Sqrt ( n ) ; i ++ ) { if ( prime [ i ] ) { for ( int j = i * i ; j <= n ; j += i ) { prime [ j ] = false ; } } }