Largest Prime Factor

The prime factors of $13195$ are $5, 7, 13$ and $29$.
What is the largest prime factor of the number $600851475143$?

We can find the largest prime factor of a number by checking divisibility starting from the smallest possible prime number, which is 2. You check if it is divisible by the prime numbers including 2, 3, 5, 7, and so on.

But in this case, the number $600851475143$ is quite large. That makes manual calculations impractical. Applying theoretical methods, like the Pollard rho algorithm for factorization, will be much faster, but they require a good deal of mathematical understanding. However, for this problem, we can provide a simple Python program that will provide the answer:

“`python
def max_prime_factors(n):
# This function returns the max prime factor
maxPrime = -1

while n % 2 == 0:
maxPrime = 2
n >>= 1 # equivalent to n /= 2

while n % 3 == 0:
maxPrime = 3
n = n / 3

for i in range(5,int(n**0.5)+1,6):
while n % i== 0:
maxPrime = i
n = n / i
while n % (i + 2) == 0:
maxPrime = i + 2
n = n / (i + 2)

if n > 4:
maxPrime = n

return int(maxPrime)

# Provide the number as an input to the function
max_prime_factors(600851475143)
“`

After running the above program, you’ll find that the largest prime factor of the number $600851475143$ is $6857$.

More Answers: