Express a number as sum of 2 primes

Question

Problem: Given an even number (greater than 2), return two prime numbers whose sum will be equal to given number.

NOTE 1: A solution will always exist. (Goldbach's conjecture)

Note 2: If there are more than one solutions possible, return the lexicographically smaller solution.

This solution becomes slower for higher order numbers. How can I optimise this code?

import math
# Function to create a list of all prime numbers uptil given number
def list_prime(A):
    primes = []  # initialise an empty list of primes
    bool_a = [True for i in range(2,A+3)]  # creates boolean list of index 
    for  i in range(2, int(math.sqrt(A))+1):  
        if bool_a[i]:
            for j in range( i * i, A +1 , i):  # eliminate all multiples of i*i+i, i*i+2i and so on uptil A+1    
                if bool_a[j]:
                    bool_a[j] = False;

    for i in range(2,A):  # the index of reamaining bools are prime numbers 
        if bool_a[i]:
            primes.append(i)

    return primes

#Function that returns two prime numbers whose sum is equal to the given number
def prime_sum(A):
    solution_set = []

    for i in (list_prime(A)):
        for j in (list_prime(A)[::-1]):
            if i + j == A:
                solution_set.append((i,j))
                break

    return min(solution_set)

Answer 1

Using the Sieve of Eratosthenes seems like a reasonable way to generate a large number of primes.

One thing that you could do is directly return your bitset representation of the primes, rather than copying it to a condensed list. This would save a bit of time in the short term, and be helpful for the next step.

---

for i in (list_prime(A)):
    for j in (list_prime(A)[::-1]):

A few comments.

First, doing something twice is slower than doing it once! Since list_prime(A) is repeated in both lines, it will have to re-run the Sieve of Eratosthenes: even though you know that the list of prime numbers isn't going to change, Python doesn't! Even worse, because the second line is in a loop, you're running list_prime again for every value of i. So you can speed it up a bit by storing that list in a variable before you get to the loops.

Second, when you have nested loops like this, you make your algorithm quadratic in the size of list_prime(A). The issue is that you're doing the imprecise test for j before the precise test, which is normally the slow way around. That is, you're considering all the values of j which meet the rule "j is a prime number" and then testing whether "j + i == A". Instead consider all the values of j for which "j + i == A" first. There is exactly one of those for each i, which is found by simple subtraction. Then check whether that j is in your list of prime numbers. If so, you have a match. If not, you can immediately check the next i.

(The reason that I suggested returning the bitset representation of the list of primes is that it makes it much faster to check whether a specific number is prime.)

---

A few less substantial optimisations

solution_set.append((i,j))

It is good to consider the tie-breaking rules for problems like this, and listing candidates first and checking which wins afterwards is a valid way to do so.

However, it is worth thinking about the order of your algorithm before implementing the tie-breaking check. If, as is the case here, the first satisfying value is guaranteed to be the one that wins the tie break because it has the smallest i value, you might as well just return the first one you get to.

---

if bool_a[j]:
    bool_a[j] = False;

If the end result of these two lines is that bool_a[j] must be False, just set it to false. if statements are surprisingly slow on modern CPUs.

---

primes.append(i)

Whenever you find yourself appending something to a list one element at a time, consider whether you can rewrite it using list comprehensions. For example something like the following:

primes = [index for (index, is_prime) in enumerate(bool_a) if is_prime]

(However, as above, my actual recommendation is that you completely remove that step and directly return bool_a)

Answer 2

Restating and condensing what @Josiah already said in their answer:

1. Don't do unnecessary calculations. This includes not re-doing the calculations for all prime as well as not going through all pairs of numbers just to find two that sum to the final number.

2. Simplify the sieve of Eratosthenes to be a generator that yields each prime number as it finds it.

With these two changes your code would become:

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 sum_of_primes(n):
    primes = list(prime_sieve(n))
    # for fast `in` lookups:
    primes_set = set(primes)
    for a in primes:
        b = n - a
        if b in primes_set:
            # this is the lexicographically smallest by design
            return a, b

This outperforms your original code by a huge margin:

In [5]: %timeit prime_sum(1002)
27.1 ms ± 256 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [6]: %timeit sum_of_primes(1002)
142 µs ± 699 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

It also scales a lot better (O(n) instead of O(n^2)):