大素数

Question

指令计算给定自然数的素数因子。

一个素数只能被它自己和1整除。

注意，1不是素数。

例如，60的主要因素是什么？

我们的第一个除数是2.2到60，剩下的是30。2到30，剩下15. 2不干净地变成15。所以让我们转到我们的下一个除数，3.3干净地变成15，剩下的5.3没有干净地变成5。下一个可能的因子是4.4没有干净地变成5。下一个可能的因子是5.5确实是干净的5。我们只剩下1，所以现在，我们完成了。在计算中，我们成功的除数表示60: 2、2、3和5的素因子的列表。

你可以亲自检查一下：

2*2*3*5=4* 15 = 60成功！

我的代码：

def factors(value):
    y = []
    x = [i for i in range(2,value+1) if value%i ==0]
    print(x)
    while value !=1:
        for i in x:
            while value%i==0:
                y.append(i)
                value = value/i
  
    return y

它通过了所有的测试，除了一个。值= 93819012551。程序就这么冻结了。我该怎么处理大数字，这样它才不会冻结？谢谢

Answer 1

一旦到达剩余数字的平方根，就可以停止检查因子。在这一点上，剩余的数保证是素数(或1)。此外，您应该使用整数除法(//)来减少值。

例如：

def factors(value):
    f,inc  = 2,1   # factor, increment (skips multiples of 2 & 3)
    result = []
    while f*f<=value:                     # up to √remaining
        while value%f == 0:               # add divisors
            result.append(f)
            value //= f                   # reduce target value
        f,inc = f+inc,2 if f<5 else 6-inc # next factor (2,3,5,7,11,...)
    if value>1: result.append(value)      # remainder is prime if >1
    return result

print(factors(93819012551)) # [11, 9539, 894119]