# How does this largest prime factor finding algorithm work?

I saw this YouTube video online where this guy finds the largest prime factor of a number using a seemingly simple approach, but I don't quite understand the math of it. Here's the link https://m.youtube.com/watch?v=5kv9q7qgvlI The code -

``````n=1234 # Some number whose largest factor I want to find
i=2 # It seems that he tries to start from the smallest prime number
while i**2<n: # I don't understand this part where he checks if the square of variable is less than the target number
while n%i==0: # I know this checks if n is divisible by i
n/=i
i+=1 # increments i's value
print(n)
``````

I know that this code works, but why? I get the last two lines, but why is it necessary to check if the square of variable i is less than n?

If your number `N` is divisible by `I` (in other terms, `I` being a factor of `N`), and `I` is greater than `sqrt(N)`, then there must be another factor of `N`, call it `J = N/I`, being smaller than `sqrt(N)`.

If you exhaustively searched all potential factors up to `I`, you must have already found `J`, so you covered that factorization earlier.

We are looking for the largest prime factor, so the question remains whether the final `N` when terminating the loop is a prime number.

Whenever we encountered a factor of `N`, we divided `N` by this factor, so when considering a potential factor `I`, we can be sure that the current `N` won't have any factors below `I` any more.

Can the final `N` when terminating the loop be composed from more than one factor (i.e. not being prime)?

No.

If N isn't prime, it must be composed from `K` and `L` (`N = K * L`), and `K` and `L` must be both bigger than `sqrt(N)`, otherwise we would have divided by `K` or `L` in an earlier step. But multiplying two numbers, each bigger than `sqrt(N)`, will always be bigger than `N`, violating `N = K * L`.

So, assuming that the final `N` wasn't prime, runs into a contradiction, and thus we can be sure that the final `N` is a factor of the original `N`, and that this factor is indeed a prime number.