如何计算给定数的质因数的指数？

Question

我刚刚完成了第 3 个项目欧拉问题，该问题要求您找到给定数字的最大质因数。我创建了一个函数，其中 return 列出了一个数字的所有质因数。

例如，如果您输入 100，它将 return [2.0, 5.0]

我现在想尝试制作一个程序，其中 return 是一个列表，其中主要因子出现的次数与其指数相同。

例如，输入 100 将改为 return [2.0, 2.0, 5.0, 5.0]（因为 100 是 2^2 * 5*2）。

我编写了一个函数，如果放入一个包含质因数的列表和一个包含指数的列表，它可以正确地执行此操作。问题是我用来获取指数列表的函数是错误的。

我编写的代码对某些数字（18、36、50、54...）失败。

我对编程还很陌生，所以如果有人能帮助我，我将不胜感激。

def p_fctr_exp(n):
    """Prime factorises n and gives the exponents of each factor"""
    l1 = prime_factors(n) #Initialisation of variables and lists ('prime_factors() ) is just the function I made which gives a list of the prime factors
    p = 1
    exp=[]
    result=[]
    for x in l1:    #This multiplies the prime factors together just once
        x = float(x)
        p = (p * x)
    for x in range(0,len(l1)):  
        """Loop which cycles through factors from smallest first and multiplies 
    the total by the factor until the point where one more would make it bigger
    than the target number. The number of cycles required is stored in the 
    list 'exp'""" 
        a=1
        while p<n:
            p = p*float(l1[x])
            a+=1
        if p == n:
            exp.append(a)
        elif x < len(l1)-1:
            exp.append(a-1)
    return exp

我认为问题出现在 while 循环中，因为它的工作原理是将乘积 p 乘以最低的质因数，直到它变得太大，然后向上移动到下一个质因数。问题是如果说正确的指数应该是 2，但是将它增加到 3 并不会使乘积大于目标数。

我觉得这可能是解决问题的完全错误的方法，但我对要更改的内容犹豫不决。

Answer 1

既然您想知道这是否是解决问题的正确方法，我建议您编写一个类似的函数来计算质因数，只需将它们中的每一个添加到列表中即可：

def prime_factors_list(n):
    result = list()
    diviser = 2

    if n <= 0:
        return [] #empty list



    if n == 1:
        return [1]

    """We increment diviser when it does not divide n anymore"""
    while n != 1:
        if n % diviser == 0: # if 'diviser' divides n
            n = n / diviser
            result.append(diviser) # diviser works, we add it to the list
        else:
            diviser += 1 #diviser does not work, we try with a bigger one

    return result

Answer 2

您应该使用取模运算符 %。假设您有一个数字 270。因此，您将 270 除以 3，直到它与 3 相差 "stripped"，即。没有 3 的因数了。

270/3=90
90/3=30
30/3=10
10 不能被 3 整除。

所以，270=10 * 3³

使用质因数函数：

def p_fctr_exp(n):
    primes = prime_factors(n)
    exp=[]

    for p in primes:
        e=0
            while (n%p==0):
            n=n//p       # since p still divides n,
            e+=1         # we divide n by p and increase the exponent
        exp.append(e)
    return exp

注释

不要在数论问题中使用浮点数。首先，模运算符对它们不起作用。其次，您永远不知道什么时候您会成为精度不准确的受害者。示例：0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1==1.0 的计算结果为 False. 如果您需要检查整除性，请使用 %.
您的代码失败的原因是正确的。对于 18，prime_factors(18)=[2,3]. 因为 2⁴ < 18 < 2⁵。您的函数报告 2 的 18 次方是 4，这是错误的。

Answer 3

这将完成工作。

可能 faster ways to do this 权衡 cpu 的内存使用。在这里，如果足以进行因式分解，我会尝试将素数列表保持在较小的范围内。

import math

class PrimeList():
    init_primes = [2,3,5,7,11,13,15,17,19,23]
    def __init__(self, n):
        self.primes = PrimeList.init_primes
        self.extend(n)

    def extend(self,n):
        n = int(n)
        nextnum = self.primes[-1]
        while(self.primes[-1]<n):
            nextnum += 2
            if self.check(nextnum):
                self.primes.append(nextnum)

    def check(self,n):
        n = int(n)
        limit = int(math.sqrt(n))
        return all((n%p for p in self.primes if p<=limit))

    def is_prime(self, n):
        n = int(n)
        self.extend(int(math.sqrt(n)))
        return self.check(n)

    def factors(self, n):
        n = int(n)
        x = n
        fact = dict()
        for p in self.primes:
            if p>x:
                break
            while x%p==0:
                x = x/p
                fact[p]=fact.get(p,0)+1
        if x>1:
            e = x if x!=n else int(math.sqrt(n))
            self.extend(e)
            return self.factors(n)
        return sorted(fact.items())



myprimes = PrimeList(25)
print "cached primes:"+str(myprimes.primes)
print "100 == "+str(myprimes.factors(100))
print "32768 == "+str(myprimes.factors(32768))
print "23! == "+str(myprimes.factors(math.factorial(23)))
print "cached primes: "+str(myprimes.primes)
print "10001 == "+str(myprimes.factors(10001))
print "cached primes:"+str(myprimes.primes)

输出：

cached primes:[2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29]
100 == [(2, 2), (5, 2)]
32768 == [(2, 15)]
23! == [(2, 19), (3, 9), (5, 4), (7, 3), (11, 2), (13, 1), (17, 1), (19, 1), (23, 1)]
cached primes: [2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29]
10001 == [(73, 1), (137, 1)]
cached primes:[2, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137]

如何计算给定数的质因数的指数？

How to calculate the exponents of prime factors for a given number?

python

prime-factoring

exponent