algorithm - What makes this prime factorization so efficient? -

i've been doing project euler problems learn/practice lua, , initial quick-and-dirty way of finding largest prime factor of nwas pretty bad, looked code see how others doing (in attempts understand different factoring methodologies).

i ran across following (originally in python - lua):

function main()     local n = 102     local = 2     while i^2 < n         while n%i==0 n = n / end         = i+1     end     print(n) end 

this factored huge numbers in very short time - immediately. thing noticed algorithm wouldn't have divined:

• n = n / i

this seems in of decent algorithms. i've worked out on paper smaller numbers , can see makes numbers converge, don't understand why operation converges on largest prime factor.

can explain?

in case, i prime factor candidate. consider, n composed of following prime numbers:

n = p1^n1 * p2^n2 * p3^n3 

when i reaches p1, statement n = n / = n / p1 removes 1 occurrence of p1:

n / p1 = p1^(n-1) * p2^n2 * p3^n3 

the inner while iterates long there p1s in n. thus, after iteration complete (when i = + 1 executed), occurrences of p1 have been removed and:

n' =  p2^n2 * p3^n3 

let's skip iterations until i reaches p3. remaining n then:

n'' = p3^n3 

here, find first mistake in code. if n3 2, outer condition not hold , remain p3^2. should while i^2 <= n.

as before, inner while removes occurences of p3, leaving n'''=1. second mistake. should while n%i==0 , n>i (not sure lua syntax), keeps last occurence.

so above code works numbers n largest prime factor occurrs once successivley removing other factors. other numbers, mentioned corrections should make work, too.