CODEWITHSUNDEEP
pythonpython-3.x
Trent Fowler
Trent Fowler

Reputation: 103

Trying to understand a solution to project Euler # 3

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? @ http://projecteuler.net/problem=3

I have a deal going with myself that if I can't solve a project Euler problem I will understand the best solution I can find. I did write an algorithm which worked for smaller numbers but was too inefficient to work for bigger ones. So I googled Zach Denton's answer and started studying it.

Here is his code:

#!/usr/bin/env python
import math

def factorize(n):
    res = []
    # iterate over all even numbers first.
    while n % 2 == 0:
        res.append(2)
        n //= 2
    # try odd numbers up to sqrt(n)
    limit = math.sqrt(n+1)
    i = 3
    while i <= limit:
        if n % i == 0:
            res.append(i)
            n //= i
            limit = math.sqrt(n+i)
        else:
            i += 2
    if n != 1:
        res.append(n)
    return res

print max(factorize(600851475143))

Here are the bits I can't figure out for myself:

  1. In the second while loop, why does he use a sqrt(n + 1) instead of just sqrt(n)?
  2. Why wouldn't you also use sqrt(n + 1) when iterating over the even numbers in the first while loop?
  3. How does the algorithm manage to find only prime factors? In the algorithm I first wrote I had a separate test for checking whether a factor was prime, but he doesn't bother.

Upvotes: 0

Views: 158

Answers (1)

NPE
NPE

Reputation: 500773

  1. I suspect the +1 has to do with the imprecision of float (I am not sure whether it's actually required, or is simply a defensive move on the author's part).

  2. The first while loop factors all twos out of n. I don't see how sqrt(n + 1) would fit in there.

  3. If you work from small factor to large factors, you automatically eliminate all composite candidates. Think about it: once you've factored out 5, you've automatically factored out 10, 15, 20 etc. No need to check whether they're prime or not: by that point n will not be divisible by them.

I suspect that checking for primality is what's killing your original algorithm's performance.

Upvotes: 2

Related Questions