All multiples of i are composite ( and divisible by i ) so add i to their prime factorization getpow ( j , i ) times
for j in range ( i * i , n + 1 , i ) : NEW_LINE INDENT if SPF [ j ] == j : NEW_LINE INDENT SPF [ j ] = i NEW_LINE DEDENT DEDENT