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

Question

I just completed the 3rd project Euler question which asks you to find the largest prime factor of a given number. I made a function which returns a list of all the prime factors for a number.

For example, if you input 100 it would return [2.0, 5.0]

I want to try and now make a program which returns a list with the prime factors appearing the same number of times as their exponent.

So for example, inputting 100 would instead return [2.0, 2.0, 5.0, 5.0] (because 100 is 2^2 * 5*2).

I have written a function which does this correctly if a list containing the prime factors and a list containing the exponents are put in. The problem is that the function I have used to get the list of exponents is wrong.

The code I have written fails for certain numbers (18, 36, 50, 54...).

I am fairly new to programming so if anybody could help me out I would really appreciate it.

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

I think the problem occurs in the while loop since it works by multiplying the product p by the lowest prime factor until that becomes too big and then moving up to the next prime factor. The problem is if say the correct exponent should be 2, but increasing it to 3 doesn't make the product bigger than the target number.

I have a feeling this is probably just completely the wrong way of solving the problem but I'm stuck on what to change.

Answer 1

This will get the job done.

There may be faster ways to do this that tradeoff memory usage for cpu. Here I've attempted to keep the primes list small if it suffices for the factorization.

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)

Output:

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]

Answer 2

You should use the modulo operator %. Say you have a number 270. So, you divide 270 by 3 until it is "stripped" off 3's, ie. has no factors of 3 left.

• 270/3=90
• 90/3=30
• 30/3=10
• 10 is not divisible by 3.

So, 270=10 * 3³

Using you prime factors function:

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

Notes

1. DO NOT use floats for number theory problems. First, modulo operator doesn't work on them. Second, You never know when you are victim of inaccurate precision. Example: 0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1==1.0 evaluates to False. If you need to check divisibility use %.

2. You are right on the reason your code fails. For 18, prime_factors(18)=[2,3]. since 2⁴ < 18 < 2⁵. Your function reports that the power of 2 in 18 is 4 which is wrong.

Answer 3

Since you were wondering if it was the right way for solving the problem, I would suggest you to write a similar function for calculating prime factors, simply adding each one of them to the list:

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