5
\$\begingroup\$

I have been trying to learn Python and just solved Euler Problem 3:

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

What is the largest prime factor of the number 600851475143 ?

I am looking for any feedback on improving efficiency and the code itself.

My code:

from itertools import count, islice

def is_prime(number):
    for n in islice(count(2), int(number**0.5 -1)):
        if number % n == 0:
            return False
    return True


def find_factors(number):
    lst = []
    for n in islice(count(2), int(number/2-1)):
        if number % n == 0:
            if is_prime(n):
                lst.append(n)
    return lst


print(find_factors(13195).pop())

I used islice instead of xrange because of int limits, which I learned about from another question at StackOverflow.com

In code above, I have created two separate functions, one to find a prime and the other to find factors.

The program works this way,

  • It takes an input number
  • Find all the factors of that number from 2->number/2
  • If it finds a factor, it checks if its a prime, and append it to a list.
  • Eventually I print the last element of list since list in python are ordered.
\$\endgroup\$
  • \$\begingroup\$ There are far more efficient methods to get the result. I suggest to have a look at other Q&A's about the same problem. \$\endgroup\$ – Martin R Aug 24 '18 at 2:03
  • \$\begingroup\$ Thank you for your response Martin. I have already seen other solution. My goal is to not solve the problem, my goal is to learn to code more efficiently and find where i lack. Of course, I can just follow what others did. But I want to learn how can I improve my own code. After that I will definitely follow other efficient solutions. I hope this makes sense. \$\endgroup\$ – MaverickD Aug 24 '18 at 2:12
  • 2
    \$\begingroup\$ If you're talking about Python 3.x, there is no xrange() — that's only in Python 2.x. \$\endgroup\$ – 200_success Aug 24 '18 at 2:17
  • \$\begingroup\$ Technically, you haven't really solved Project Euler Problem 3, since you've just demonstrated the given example of 13195. Your algorithm is much too inefficient to work for 600851475143. You really could benefit from looking at other answers about the same problem. \$\endgroup\$ – 200_success Aug 24 '18 at 2:29
8
\$\begingroup\$

When I look at your solution, the first impression I get is that it's too complicated. To solve the problem you don't need any fancy algorithms for prime numbers, or islice and count. It's a simple task of trying to divide by possible factors.

One important thing to note is that we only need to check for prime factors that are smaller than the square root of the number. Once we have reached the square root, there can be only one remaining factor, which can be proved by contradiction.

Another important thing to note is that once we have found a prime factor, we can divide the original number by that factor and reduce our problem size.

Doing both of these things, I end up with something like this:

def get_max_prime_factor(n):
    d = 2
    factors = []
    while d*d <= n:
        while n%d == 0:
            n //= d
            factors.append(d)
        d += 1
    if n != 1:
        factors.append(n)
    return max(factors)

Now, I'll say that even this implementation might be too complicated, since I'm saving all prime factors in a list instead of only keeping track of the largest one. If you want you could change that implementation and make it even more efficient, but to solve the problem above it's not necessary.

\$\endgroup\$
  • \$\begingroup\$ @TobySpeight Good catch, I'll change it. \$\endgroup\$ – maxb Aug 24 '18 at 10:25
4
\$\begingroup\$

Another, slightly slower, approach, but which helps you in future Project Euler problems, is using the same algorithm as in the answer by @maxb, but instead of dividing by every number, only divide by the primes up to \$\sqrt{n}\$. For this you can use a prime sieve (a fast method to get all primes up to some number):

def prime_sieve(limit):
    prime = [True] * limit
    prime[0] = prime[1] = False

    for i, is_prime in enumerate(prime):
        if is_prime:
            yield i
            for n in range(i * i, limit, i):
                prime[n] = False

def prime_factors(n):
    for p in prime_sieve(int(n ** 0.5) + 1):
        while n % p == 0:
            n //= p
            yield p
    if n != 1:
        yield n

if __name__ == "__main__":
    for n in (13195, 600851475143):
        print(n, max(prime_factors(n)))

Here I used a basic implementation of the sieve of Eratosthenes in pure Python. Faster implementations exist.

Some speed comparisons:

%timeit max(prime_factors(13195))
19.2 µs ± 771 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit get_max_prime_factor(13195)
3.55 µs ± 68.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit find_factors(13195).pop()
873 µs ± 217 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

And for the actual number in the problem:

%timeit max(prime_factors(600851475143))
120 ms ± 1.54 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit get_max_prime_factor(600851475143)
394 µs ± 6.68 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit find_factors(600851475143).pop()
running for more than 10 minutes...
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.