Problem 3

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

What is the largest prime factor of the number 600851475143 ?

Solution 1: Brute forcing

It is wasting to iterate through all natural numbers to 600851475143 and check if divisible by iter and iter is prime. So we just iterate through all natuaral numbers to square root of 600851475143 since two primes greater than the square root is also greater than the number.
So,

num = 600851475143
i = 2


while i <= num**0.5:
  

Now we need to check if the number is divisible by iteration. If we get a number that divedes, reduce our question to lowest number and our iteration continue from there.
Here is the code

num = 600851475143
i = 2

while i <= num**0.5:
    
    # Python would optimize this!
    # Removing would make the code
    # slower but readable.
    while num%i:
        i += 1

    # Reducing num to not multiple of i
    while num%i == 0:
        num //= i

    i += 1


print(num)

The output: 6857.
This run ~0.0s.

Solution 2: Improved

The above took 1473 iterations before getting the answer. The number iterations depends on number of divisors that number have. In the worst case, when the number is prime number of iterations is equal to the number itself(not even its square root?). We can improve the worst case(at least to square root) and number of iterations by jumping over divisible of 2 which will reduce the number of iterations by half.



n = 600851475143
num = n

# To jump over multiples of 2.
# Since num would be not multiple of 2,
# multiples of 2 cant be factor
i = 2
while not num%i:
    num //= i

i = 3             
while i <= num**0.5:
    # Reducing num to not multiple of i
    while not num%i:
        num //= i

    i += 2

if num ==  n:
  print("No Factor!")
else:
  print(num)