Prime factorisation program in python gives no output

Question

I am working on Project on Euler Problem 3,

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

The code that I came up with is as follows:

def q_prime(a):
    if a == 2:
            return True
    elif a < 2:
            return False

    for i in range(2,a):


            if a%i == 0:
                    return False
    else:
            return True


def prime_factor(x):
    prime_factors =[]
    for i in range(1,x):
            if q_prime(i) == True and x%i == 0:
                    prime_factors.append(i)
    return prime_factors

Calling this function of 13195 gave me [5,7,13,29] as expected. I tried some other combinations like 1035 which gives [3,5,23]. However, when I call this function on 600851475143, I get no output. Moreover, I get no error message either. It runs for a while, and simple restarts shell

I know this is not an elegant code, and I am guessing brute forcing my way through a problem like this for a large number is causing this problem? What exactly is going on?

Answer 1

Number 600851475143 is too big. You can simplify computations if in q_prime and in prime_factor you will check number not in range [2, n] bun in range [2, sqrt(n)+1]. This will also return correct result but takes less time:

import math

def q_prime(a):
    if a == 2:
            return True
    elif a < 2:
            return False

    for i in range(2, int(math.sqrt(a) + 1)):
            if a%i == 0:
                return False
    else:
        return True


def prime_factor(x):
    prime_factors =[]
    for i in range(1, int(math.sqrt(x) + 1)):
            if q_prime(i) == True and x%i == 0:
                    prime_factors.append(i)
    return prime_factors

Answer 2

Both the functions that you have written are problematic given the size of the problem. q_prime(a) loops to a and prime_factor(x) loops to x calling q_prime every iteration. That makes your algorithm O(N^2) which is way too much for a number like 600851475143.

Better approach (O(√N) -> essentially immediate result):

• generator function using sieve of Eratosthenes yielding prime numbers
• loop through primes until sqrt(n) collecting factors while shrinking n with each factor found
  • add n itself if no other factors where found

Answer 3

Here is what happens when I try to run your code using Python 2.7:

$ python primes.py
Killed: 9

The issue is that range(2, 600851475143) tries to create a list of 600851475141 elements. This is too large to fit in your computer's memory, so the Python program gets killed.

You could try replacing range() with xrange(), but your program will take too long to complete. You need a better algorithm.

P.S. There's also a bug in your code which means that it doesn't work for prime inputs.