Прайм факторизация большого числа

Question

Я пытаюсь создать программу для простой факторизации числа, и вот код, который я придумал.

def primeFactors(n):
    l=[]
    ss=0
    for i in range(2,n,1):
    #checking for prime
        t=0
        for j in range(2,i):
            if(i==2):
                continue
            if(i%j==0):
                t=t+1   
        if(t>0):
            continue
        else:
            if(n==0):
                break
            else:
                print(i)
                if(n%i==0):
                    n=n//i
                    ss=ss+1
                    i=i-1
                if(n%i!=0 and ss>0):
                    l.append(i)
                    l.append(ss)
                    ss=0
                else:
                    continue
    q=""
    for i in range(0,len(l),2):
        q=q+"("+str(l[i])+"**"+str(l[i+1])+")"
    return q

Работа кода выглядит следующим образом:

1. Он проверяет, является ли число во внешнем l oop простым числом.
2. Если это простое число, то он проверяет, приведет ли деление числа с n к остаток от 0 или нет, если это так, разделите его.
3. Приращение ss, которое представляет собой число раз, которое простое число будет использоваться во всей факторизации. Кроме того, уменьшите значение i, чтобы при увеличении в конце l oop оно оставалось таким же, чтобы снова проверить, может ли i делить n или нет.
4. Если он не может разделить и ss (количество раз i может разделить) больше 0, тогда мы добавляем его в список.

Я получаю ошибки тайм-аута в этом и не могу понять, как на go о его исправлении.

Любая помощь приветствуется

Answer 1

Вы можете увеличить i, только если i не делит n. Кроме того, вы можете просто проверить до квадрата root из n, так как если i делит n, то i <= sqrt(n).

Пример:

import math

def prime_factors(n):

    i, factors = 2, []

    while n > 1 and i <= int(math.sqrt(n)):
        if n%i == 0:
            n/=i
            factors.append(i)
        else:
            i+=1

    if n > 1:
        factors.append(int(n))

    return factors


>>> prime_factors(64)
[2, 2, 2, 2, 2, 2]
>>> prime_factors(28)
[2, 2, 7]
>>> prime_factors(31)
[31]

Примечание . Вам не нужно проверять, является ли i простым числом. i не может быть не простым, так как если бы i не было простым, тогда существовал бы j < i, который делит i с j, являющимся простым. Поскольку i переходит от 2 к sqrt(n), он встречался бы раньше в l oop.