8
\$\begingroup\$

So I am essentially a complete newbie to programming, and have been attempting to learn Python by completing the Project Euler problems. I haven't gotten very far, and this is my code for problem #3 :

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

Although my solution works, I'd like to know how I can improve.

primes = [2]
factors = []

def isPrime(x):
    a = 1
    if x == 1:
        return False
    while a < x:
        a += 1
        if x % a == 0 and a != x and a != 1:
            return False
            break
    return True

def generatePrime():
    a = primes[-1]+1
    while isPrime(a) == False:
        a += 1
    primes.append(a)

def primeFactor(x):
    a = primes[-1]
    while a <= x:
        if x % a == 0:
            factors.append(a)
            x /= a
        generatePrime()
        a = primes[-1]

primeFactor(input("Enter the number: "))
print("The prime factors are: " + str(factors) + "\nThe largest prime factor is: " + str(sorted(factors)[-1]))
\$\endgroup\$
  • \$\begingroup\$ You should replace while a < x: with while a < math.sqrt(x): You can also check whether x is even and > 2, in that case it is not a prime, also google for 'prime sieve'. \$\endgroup\$ – konijn Mar 4 '13 at 14:06
5
\$\begingroup\$

You can save quite a bit time on your prime generation. What you should keep in mind is that a prime is a number which is no multiple of a prime itself; all other numbers are.

So in your isPrime function you can just go through your primes list and check if each prime is a divisor of the number. If not, then it is a prime itself. Of course you would need to make sure that you fill your primes list enough first.

As the most basic idea, you only need to check until sqrt(n), so you only generate numbers this far. And you can also just skip every even number directly. You could also make similar assumptions for numbers dividable by 3 etc., but the even/uneven is the simplest one and enough to get fast results for not too big numbers.

So a prime generation algorithm, for possible prime divisors up to n, could look like this:

primes = [2]
for i in range(3, int(math.sqrt(n)), 2):
    isPrime = not any(i % p == 0 for p in primes)
    if isPrime:
        primes.append(i)

Then to get the prime factors of n, you just need to check those computed primes:

primeFactors = []
m = n
for p in primes:
    while m % p == 0:
        m = m / p
        primeFactors.append(p)
    if m == 0:
        break

print('The prime factorization of `{0}` is: {1}'.format(n, '×'.join(map(str,primeFactors))))

For the euler problem 3 with n = 317584931803, this would produce the following output:

The prime factorization of 317584931803 is: 67×829×1459×3919

\$\endgroup\$
  • \$\begingroup\$ If you are not going to sieve to calculate your primes, you should at least bring together your prime calculation and factor testing together, so that as soon as you find the 67 factor, your largest prime to calculate is reduced from 563546 to 68848, and by the time you know 829 is a prime to 2391, and once 1459 is known as a prime you don't calculate any more primes to test as factors. \$\endgroup\$ – Jaime Mar 4 '13 at 18:42
  • \$\begingroup\$ @Jaime Sure, you can again save a lot when combining those two. My original solution for problem 3 (which btw. doesn’t even require factorization) is a lot more concise too. But given OP’s original code structure I thought it would make more sense to show separated and reusable pieces. With my example I could once generate the primes and then just run the factorization against multiple numbers. \$\endgroup\$ – poke Mar 4 '13 at 19:19

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.