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