Function to precompute shortest prime factors
def sieve ( ) : NEW_LINE INDENT i = 2 NEW_LINE while ( i * i <= 100006 ) : NEW_LINE INDENT for j in range ( i , 100006 , i ) : NEW_LINE INDENT if ( spf [ j ] == - 1 ) : NEW_LINE INDENT spf [ j ] = i ; NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT