python中素数分解的指数形式 [英] Exponential form of prime factorization in python

问题描述

我必须以指数方式将正整数转换为其质因数分解形式.例如:[(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 case n = 10. Can run on others also.

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