🔒 Problem

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

🔐 Key Idea

prime factorization algorithm into code

🔑 Solution

🧭 Initial idea

O(n²) complexity, brute force method.

Doesn't end under 1 minute.

n = 600851475143

def is_prime(n):
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i is 0:
            return False
    return True

max = 0

for i in range(3, n, 2):
    if i % 3 is 0 or i % 5 is 0 or i % 7 is 0:
        continue
    
    if n % i is 0:
        if is_prime(i):
            max = i

print(max)

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-14-3bf7fcdc1e29> in <module>
     13         continue
     14 
---> 15     if n % i is 0:
     16         if is_prime(i):
     17             max = i

KeyboardInterrupt:

Why did I get it wrong?

I forgot how to do prime factorization. 😓

➗ Prime factorization with division method

👨‍🏫 How to do prime factorization with division

Prime factors | Remainder
            2 |        40
            2 |        20 (= 40 / 2)
            2 |        10 (= 20 / 2)
            5 |         5 (= 10 / 2)
              |         1 (= 5 / 5)

🧾 Pseudocode

while n > 1:
    find number i that makes n % i == 0:
        n = n / i
        restart i from 2

n = 600851475143

max = 0
i = 2

while n > 1:
    if n % i is 0:  # prime factor found
        n = n // i
        if i > max:
            max = i
        i = 2
        continue
    
    i += 1

print(max)

6857

Note: We don’t have to check whether i is prime or not, because we are iterating i from 2, therefore the factor will always be the smallest prime factor for the current n. And also, we can skip the if i > max check because the last factor that divides n to 1 will be the biggest factor.

Important: In Python, 0 and 0.0 is different. Evaluating 0 is 0.0 will return False.