Decompose any number to its prime factors raised to their respective powers

Question

A simple code which takes the given number as input and gives all of its prime factors raised to their respective powers. It works well up to 10⁶; after that it slows down greatly for some numbers. But it works smoothly for numbers which don't have many prime factors

Here's the code:

x=int(input("Enter number:"))
c=[]    #load the exponential powers here
b=[]    #load the primes here
i,k,f=0,0,2
l=100
def primes(i,n):            #returns all primes between i and n
    primes = []
    for possiblePrime in range(i,n+1): 
        isPrime = True
        for num in range(2, int(possiblePrime ** 0.5) + 1):
            if possiblePrime % num == 0:
                isPrime = False
                break
        if isPrime:
            primes.append(possiblePrime)
    return(primes)

while x!=1:
    try:
        while x%b[k]==0:            #extract every prime from the number and store their resp exp powers
            i+=1                    #counts the power of the prime stored in b[k]
            x=x//b[k]               #Removes the prime number from the given number
        k+=1
        c.append(i)
        i=0
    except IndexError:              #if list of primes are not enough...add more of them
            b=b+primes(f,l)         
            l+=10000

print("Prime Numbers:    ",[b[i] for i in range(len(c)) if c[i]!=0])   #prints the primes    
c=[c[i] for i in range(len(c)) if c[i]!=0]        
print("Respective Powers: ",c)                                          #prints their respective powers

Sample Output: (I just took a random number)

Enter number: 23412
Prime Numbers: [2, 3, 1951]
Respective Powers: [2, 1, 1]

This means 23412 = 2² × 3¹ × 1951¹

Also, all optimizations and improvements or suggestions are welcome.

Answer 1

The problem with your prime generator is that you don't use the previously generated primes to check if a number is prime. The idea is that every non-prime number can be "prime factorized". Which also means that if a number can't be divided by the primes smaller than it, it's a prime number. For example, if you want to see if 13 is prime, you can check if it can be divided by 2,3,5,7,11 and since it can't be divided by any of those, it's prime. That's not a big improvement for small numbers, but for big numbers, it becomes a really good improvement since you already have those primes at hand. But for this to work, you need to generate primes from 2, not from i. It's also pretty standard that limits are exclusive when you pass integer intervals, so I've changed n+1 to n in the range, but feel free to undo this.

def gen_primes(n):
    #Let's give us an head start.
    primes = [2]

    for possiblePrime in range(3,n): 
        for p in primes:
            if possiblePrime % p == 0:
                primes.append(possiblePrime)

    return primes

Now, you could modify this algorithm to check for [p for p in primes if p < n ** 0.5], but you'd need to check that this list isn't empty (for example if n = 3 when primes = [2]) and add the prime to your list. If you decide to implement this, you could use a more suited algorithm to filter the primes because your array is always sorted, which opens nice possibilities. Finally, to make this algorithm even smarter, we could transform it into a generator using the yield keyword. This way, you maybe wouldn't need to generate all primes to n if it's not necessary.

def gen_primes(n):
    #Let's give us an head start.
    primes = [2]
    yield 2

    for possiblePrime in range(3,n): 
        for p in primes:
            if possiblePrime % p == 0:
                primes.append(possiblePrime)
                yield possiblePrime

This way, for example, if you use gen_primes(512) to find the prime factorization of the number 512, you would only yield 2 and not all other primes between 2 and 514 (because \$512 = 2^9\$ That's a great improvement!

The rest of your algorithm would change to something like this :

n  = int(x ** 0.5)
prime_factors = []
prime_exponants = []

for prime in gen_primes(n):
    if x == 1:
        return

    e = 0
    while x % prime == 0:
        e += 1
        x /= prime

    if e > 0:
        prime_factors.append(prime)
        prime_exponants.append(e)

The main advantage of this is that you only generated the primes you need, no more, no less.

Now let's talk coding style : The python standard is snake_case, you used camelCase. It's not the end of the world, but standards are important. At least you're consistent (you didn't mix styles), which in my opinion makes it okay.

You use a lot of single letter variable names in your algorithm, it makes it harder to read. You shouldn't be shy to use meaningful names it's much easier for everyone (including yourself) to understand and debug the code.

Last thing it that I think the order in which your code is is confusing. You have code -> functions -> code, I think it'd be clearer if you defined your functions at the top of your file (obviously, after import).