Sieve of eratosthenes method to count number of unique prime factors .
int arr [ N + 1 ] ; memset ( arr , 0 , sizeof ( arr ) ) ; for ( int i = 2 ; i * i <= N ; i ++ ) { if ( ! arr [ i ] ) for ( int j = 2 * i ; j <= N ; j += i ) arr [ j ] ++ ; arr [ i ] = 1 ; }