4
\$\begingroup\$

I have a function that is able to return the factors of a number that are prime.

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

The function works great, and I was even able to improve it by dividing by just prime numbers instead of all numbers. The problem is it still isn't efficient enough because at 100,000,000 the program takes 10 seconds to finish and the number I need to run through this is 600,851,475,143 which will take more than 6000 times longer to finish.

In the spirit of the challenge, I don't want to be given the answer, but some guidance.

There are also issues with just how large the number is. If I use xrange() it will still give me an overflow error but this isn't a huge problem (I can google answers for that).

def getPrimesM(integer, start=4):
  primes = [2,3]
  for num in range(start, integer):
    if integer % num == 0:
      for i, prime in enumerate(primes):
        if num % prime == 0:
          break
        if i >= len(primes) - 1:
          primes.append(num)

  return primes
Improve this question
\$\endgroup\$
10
  • \$\begingroup\$ In python they have a for ... else structure to handle your primes.append() line. In other languages we would typically wrap the for loop in a function that returns false instead of breaking and returns true after the loop (or vice versa). You can read more about it here. \$\endgroup\$
    – twohundredping
    Jun 4, 2015 at 23:11
  • \$\begingroup\$ Once you test for divisibility by 2, you should never be testing for divisability by 4, 6, etc. Also, if F is a prime factor of N, then the prime factors of N are F plus the prime factors of (N/F). Finally, it is confusing to use the term "multiple" instead of "factor". 5 is a factor of 45; 45 is a multiple of 5. \$\endgroup\$
    – phoog
    Jun 5, 2015 at 4:05
  • \$\begingroup\$ @phoog I tried this but it even takes too long to get all the prime numbers between 1 and that large number. \$\endgroup\$
    – grasshopper
    Jun 5, 2015 at 4:51
  • \$\begingroup\$ @grasshopper Are you sure you tried that? The code you posted seems to check all numbers, not just primes. Also note that the Project Euler problem is asking only for the largest prime factor, not for all prime factors. \$\endgroup\$
    – phoog
    Jun 5, 2015 at 5:09
  • \$\begingroup\$ @phoog well maybe I am misunderstanding but I have to go through every number to see if their prime first don't I? In fact before this I built a function that gets all prime numbers in a range and it is much slower. \$\endgroup\$
    – grasshopper
    Jun 5, 2015 at 5:14

1 Answer 1

Reset to default
4
\$\begingroup\$

Your function will always report that 2 and 3 are prime factors of your number.

Trial division is a fine strategy for this problem, and it can find the factors of 600,851,475,143 quite quickly. You have to do it smartly, though. If your main loop is for num in range(start, integer): … or for num in xrange(start, integer): …, and there's no break for that loop, then you're going to be counting up to 600 billion.

Another important detail is that when you find a factor, you should use that information to reduce the integer as much as possible. If you do it correctly, then you won't need that inner loop for primality testing anymore.

Another useful tip is to test candidates 2, 3, 5, 7, 9, 11, 13, … — in other words, 2 followed by just the odd numbers. You can write that as

from itertools import chain, count

for num in chain([2], count(3, 2)):
    …
Improve this answer
\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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