问题描述
我正在尝试创建一个数的素数分解程序,这是我想出的代码.
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
代码的工作如下:
- 它检查外循环中的数字是否为素数.
- 如果它是素数,则继续检查用
n
相除的数字是否会产生 0 的余数,如果是,则将其相除. - Increment
ss
这是素数在整个因式分解中使用的次数.另外,将i
的值递减,这样当它在循环结束时递增时,再次检查i
是否可以整除n代码>与否.
- 如果它不能划分并且
ss
(i
可以划分的次数)大于0,那么我们将它附加到一个列表中.
- It checks whether the number in the outer loop is a prime or not.
- 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. - Increment
ss
which is the number of times the prime number would be used in the whole factorisation. Also, decrement the value ofi
so that when it increments at the end of the loop, it remains the same to check again whetheri
can dividen
or not. - If it cannot divide and
ss
(number of timesi
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 .
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 以
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.
这篇关于大数的质因数分解的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!