Function for finding smallest prime factors for every integer
void smallestPrimeFactors ( ) { for ( int i = 0 ; i < 100005 ; i ++ ) spf [ i ] = -1 ; for ( int i = 2 ; i * i < 100005 ; i ++ ) { for ( int j = i ; j < 100005 ; j += i ) { if ( spf [ j ] == -1 ) { spf [ j ] = i ; } } } }