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?

1 answer

  • answered 2020-05-22 12:58 Ralf Kleberhoff

    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.