When we get a prime for the first time then assign a unique smallest value to it and all of its multiples
if ( ! ( prime [ i ] > 0 ) ) { cnt ++ ; for ( int j = i ; j <= n ; j += i ) prime [ j ] = cnt ; } }