时间戳

首页 > 解决方案 > 大数的素数分解

python - 大数的素数分解

问题描述

我正在尝试创建一个用于对数字进行素数分解的程序，这是我想出的代码。

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. 它检查外循环中的数字是否为素数。
  2. 如果它是一个素数，那么它会继续检查该数除以是否n会产生余数 0，如果是，则除以它。
  3. 增量ss是在整个因式分解中使用素数的次数。此外，减少 的值，i以便在循环结束时增加时，再次检查是否i可以除以保持不变n。
  4. 如果它不能划分并且ss（可以划分的次数i）大于 0，那么我们将它附加到一个列表中。

我收到超时错误，无法弄清楚如何修复它。

任何帮助表示赞赏

标签： pythonpython-3.xprimesprime-factoring

解决方案

i只有i不除 n才能增加。此外，您可以只检查直到 的平方根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素数相除的a j。由于i从2到sqrt(n)，它会在循环之前遇到。

推荐阅读