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