Function to find two prime numbers that sum up to a given even number

Question

The Goldbach Conjecture asserts that any even number over 2 will be the sum of exactly two prime numbers. I've created a function to find two prime numbers that add up to the number entered, but would like some help streamlining it and making it more robust. One thing I would like to add is the ability to find all prime pairs that add up to the given number and append them as tuples to a list and return it. I have a separate function that will find all prime numbers lower than or equal to a given number.

def goldbach_conj(number):
    x, y = 0, 0
    result = 0
    if not number % 2:
        prime_list = list_of_primes(number)
        while result != number:
            for i in range(len(prime_list)):
                x = prime_list[i]
                if result == number: break
                for j in range(len(prime_list)):
                    y = prime_list[j]
                    result = x + y
                    print("Adding {} and {}.".format(x, y))
                    print("Result is {}".format(result))
                    if result == number: break
    return x, y 




def is_prime(number):
    if number % 2:
        # equivalent to if number % 2 != 0 because if number is
        # divisible by 2 it will return 0, evaluating as 'False'.
        for num in range(3, int(math.sqrt(number)) + 1, 2):
            if number % num == 0:
               return False
        return True
    else:
        return False



def list_of_primes(number):
    prime_list = []
    for x in range(2, number + 1):
            if is_prime(x):
                prime_list.append(x)
    return prime_list



def main():
    while True:
        usr_in = eval(input("Please enter a positive number"
                            " greater than 1: "))
        if usr_in > 1: break
        else:
            print("Number not valid.")

    prime_list = goldbach_conj(usr_in)
    print(prime_list)
    # prime_list = list_of_primes(usr_in)
    # for x in prime_list:
    #     print(x)


if __name__ == '__main__':
    main()

Answer 1

You do this:

for i in range(len(prime_list)):
    x = prime_list[i]

and then don't use i again. So this can just be for x in prime_list:. Similarly in the j loop.

Just below that, this test:

if result == number: break

It's usually preferred to put the break on a new line.

You test this condition twice in a row - to break out of the inner for loop at the bottom of it and then again here. Instead of repeating yourself like that, use itertools.product to write them as one loop:

import itertools as it    
...
for x, y in it.product(prime_list, repeat=2):
    ...
    if result == number:
        break

To save another level of nesting, you can reverse this condition at the top:

if not number % 2:

to:

if number % 2:
    return 0, 0

x, y = 0, 0

This emphasises that you don't do any work in that case. You might want to add a short comment about why you don't need to. From your title, it sounds like you might want to treat this as an error condition and do this:

if number % 2:
    raise ArgumentError("Expected an even number")

Then you can move your return inside the for loop, in place of the break. At that point, continuing the search to find all pairs is trivial: change the return to a yield, and your function will become a generator that will keep yielding every pair that works until it has exhausted the search space.

This outer loop:

while result != number:

looks unneeded and possibly buggy. If the conjecture is true, you will find a pair, return it, and this will not be tested again. If you find a counter-example disproving the conjecture, then this would just do the whole search again giving you an infinite loop instead of fame and fortune. If you change it to yield each pair instead of returning the first one, this will repeat the full sequence indefinitely unless the very last pair tested happens to work. I would just drop it.

Answer 2

You are doing an \$O(n^2)\$ search over a sorted list, which very often implies an affirmative answer to the infamous "can we do better?" question. For this particular problem, you can get \$O(n)\$ performance by simultaneously scanning from the front and back of the list of primes:

def prime_sieve(n):
    # returns all primes smaller than n
    sieve = [True] * n
    sieve[:2] = [False, False]  # 0 and 1 are not primes
    primes = []
    for prime, is_prime in enumerate(sieve):
        if not is_prime:
            continue
        primes.append(prime)
        for not_prime in range(prime*prime, n, prime):
            sieve[not_prime] = False
    return primes

def sum_of_primes(value):
    primes = prime_sieve(value)
    lo = 0
    hi = len(primes) - 1
    while lo <= hi:
        prime_sum = primes[lo] + primes[hi]
        if prime_sum < value:
            lo += 1
        else:
            if prime_sum == value:
                yield primes[lo], primes[hi]
            hi -= 1

Notice that, since generating all primes below n can be done in \$O(n \log \log n)\$ time, it is now the prime generation that dominates the total time, i.e. using this faster algorithm makes finding the pairs virtually free (when compared to finding the primes themselves).

A sample run:

>>> list(sum_of_primes(42))
[(5, 37), (11, 31), (13, 29), (19, 23)]