CODEWITHSUNDEEP
pythonalgorithmmathprimes
astroanax
astroanax

Reputation: 99

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?

Upvotes: 1

Views: 193

Answers (1)

Ralf Kleberhoff
Ralf Kleberhoff

Reputation: 7290

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.

Caveats with the original code (thanks JohanC):

The original code checks for I being strictly less than SQRT(N) (while i**2<n). That will miss cases like N=9 where its square root 3 must be included in the iteration. So, this should better read while i**2<=n.

And the code risks some inaccuracies:

  • Using floating-point division (/= operator instead of //=) might give inexact results. This applies to Python, while in languages like Java, /= would be fine.
  • In Python, raising an integer to the power of 2 (while i**2<=n) seems to guarantee exact integer arithmetic, so that's ok in the Python context. In languages like Java, I'd recommend not to use the pow() function, as that typically uses floating-point arithmetic with the risk of inexact results, but to simply write i*i.

Upvotes: 2

Related Questions