问题描述
我必须以指数方式将正整数转换为其质因数分解形式.例如:[(2,1), (5,1)] 是上面定义的 10 的正确素数分解.我有下面的代码来生成因子.现在我应该让它们成为素数,并且应该在元组中返回它们的指数.请帮助我.
I have to Convert positive integer number into its prime factorization form exponentially. For example:[(2,1), (5,1)] is the correct prime factorization of 10 as defined above.I have this below code to generate factors.Now I should make them prime and should return their exponents also in tuples . Pl help me.
def primes(n):
divisors = [ d for d in range(2,n//2+1) if n % d == 0]
return divisors
推荐答案
你可以直接按照下面的方法,时间复杂度O(n^(1/2)).
You can directly follow the following approach which is O(n^(1/2)) in time complexity.
# n is the number to be factorized
# this list holds your desired answer
prime_factors = []
# this variable iterates over prime
start = 2
while start*start <= n:
if n % start == 0:
expo = 0
while n % start == 0:
expo = expo + 1
n = n / start
prime_factors.append([start,expo])
if n > 1:
prime_factors.append([n,1])
print prime_factors
这是一个简单的迭代方法.这是运行版本 素数分解.单击右上角( fork )以运行您的测试用例n = 10.也可以在其他人身上运行.
This is a simple iterative method. Here is running version Prime Factorization. Click on right upper corner ( fork ) to run on your test casen = 10. Can run on others also.
这篇关于python中素数分解的指数形式的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!