Search code examples
pythonprime-factoring

Can this integer factorization in Python be improved?

I've seen many ways of doing integer factorizations in Python, but didn't really understand them, so I tried to do it on my own way:

def factorisation(n):
    fact = []
    i = 2
    while i <= n:   
        if n % i == 0:      
            fact.append(i)
            n //= i
        else:
            i += 1
    return fact

I think it is working, but I don't really know why the while loop from i to n... From my lesson I learnt that we have to do it from 2 to sqrt(n).

Did I misunderstand something?

Can I improve it?

Solution

  • When an integer n is not divisible by any number up to sqrt(n), that is sufficient to indicate that n is prime. In that case you won't find any additional factors other than n itself.

    So what you can do is to stop the loop at sqrt(n), and add the remaining value of n to the list of prime factors.