Function to find the least prime factor of all the numbers
void least_prime_factor ( ) { for ( int i = 1 ; i < N ; i ++ ) lpf [ i ] = i ; for ( int i = 2 ; i < N ; i ++ ) if ( lpf [ i ] == i ) for ( int j = i * 2 ; j < N ; j += i ) if ( lpf [ j ] == j ) lpf [ j ] = i ; }