python

Integer factorization in python

I've seen on this website many way 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 if from 2 to sqrt(n). Did I misunderstand something ? Can I improve it ? Thanks :)

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.