set smallest prime factor of all even numbers as 2
for i in range ( 4 , n + 1 , 2 ) : NEW_LINE INDENT SPF [ i ] = 2 NEW_LINE DEDENT for i in range ( 3 , n + 1 , 2 ) : NEW_LINE INDENT if i * i > n : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT