Precomputing Prefix array .
for i in range ( 2 , MAX , 1 ) : NEW_LINE INDENT if ( prime [ i ] ) : NEW_LINE INDENT prefix [ i ] = i NEW_LINE DEDENT else : NEW_LINE INDENT prefix [ i ] = prefix [ i - 1 ] NEW_LINE DEDENT DEDENT