大数的质因数分解 [英] Prime factorization of a big number

问题描述

我正在尝试创建一个数的素数分解程序，这是我想出的代码.

I'm trying to create a program for prime factorization of a number and this is the code I came up with.

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. Increment ss 这是素数在整个因式分解中使用的次数.另外，将i的值递减，这样当它在循环结束时递增时，再次检查i是否可以整除n与否.
4. 如果它不能划分并且ss(i可以划分的次数)大于0，那么我们将它附加到一个列表中.

1. It checks whether the number in the outer loop is a prime or not.
2. If it is a prime, then it proceeds to check whether division of the number with n would yield a remainder of 0 or not, if it does, divide it.
3. Increment ss which is the number of times the prime number would be used in the whole factorisation. Also, decrement the value of i so that when it increments at the end of the loop, it remains the same to check again whether i can divide n or not.
4. If it cannot divide and ss (number of times i could divide) is more than 0 then we append it to a list.

我在这方面遇到超时错误，无法弄清楚如何解决它.

I am getting timeout errors in this and cannot figure out how to go about fixing it.

感谢任何帮助

推荐答案

只有 i 不除 n 时，才可以增加 i.另外，您可以检查直到 n 的平方根，因为如果 i 除以 n，则 i <= sqrt(n).

You can increase i only if i does not divide n. Also, you can just check until the square root of n, since if i divides n, then 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 以 j 为质数划分 i .由于 i 从 2 到 sqrt(n)，它会在循环之前遇到.

Note. You don't need to check if i is a prime number. i cannot be not prime, since if i were not prime, then there would exist a j < i that divides i with j being prime. Since i goes from 2 to sqrt(n), it would have met before in the loop.

这篇关于大数的质因数分解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！