Факторизация чисел

Question

Задача состоит в том, чтобы написать функцию, которая складывает число в простые множители. По заданному номеру 'n' эта функция должна возвращать список кортежей p_i, c ^ i , например, если input равен 100, вывод равен (2,2), (5,2). Итак, вот как я пытаюсь это написать:

def factor(n):
c = 1
pre_ans = list()
temp_n=n
for i in range(2,temp_n+1):
    if (is_prime(i) == True) and (temp_n % i == 0):
        for j in range (2,temp_n+1):
            if (temp_n % (i ** j) == 0):
                pre_ans.append((i,j))
                temp_n /= (i **j)
        pre_ans.append((i,c))
        temp_n /= i
print(pre_ans)

Это работает неправильно, но я не могу найти ошибку: (

Answer 1

Исправлен код. Это рабочая версия

def factor(n):
c = 1
pre_ans = list()
temp_n=n
for i in range(2, n // 2 + 1):
    if (is_prime(i) == True):
        k = 1
        while temp_n % (i ** k) == 0:
            if temp_n % (i ** (k + 1)) == 0:
                k += 1
            else:
                k += 1
                break
        if k > 1:
            pre_ans.append((i, k - 1))
return pre_ans

Answer 2

Ваша общая идея в порядке. Однако есть некоторые незначительные проблемы со следующей частью вашего кода:

for j in range (2,temp_n+1):
    if (temp_n % (i ** j) == 0):
        pre_ans.append((i,j))
        temp_n /= (i **j)
pre_ans.append((i,c))
temp_n /= i

На самом деле основная проблема в том, что вам нужно выполнить итерацию в другом направлении в этом выражении for j in range (2,temp_n+1). Если переписать это как

def factor(n):
    c = 1
    pre_ans = list()
    temp_n=n
    for i in range(2,temp_n+1):
        if (is_prime(i) == True) and (temp_n % i == 0):
            for j in range (temp_n+1, 0,-1):
                if (temp_n % (i ** j) == 0):
                    pre_ans.append((i,j))
                    temp_n /= (i **j)
    print(pre_ans)

это будет работать. Весь код также может быть написан немного короче:

from collections import Counter

def factor(n):
    lst = []
    for i in range(2, n+1):
        while n % i == 0:
            lst.append(i)
            n = n / i
    return Counter(lst).items()

print(factor(100))