Goldbach's conjecture algorithm I did a Goldbach's Conjecture exercise and got it to work. It's pretty slow though and I was wondering how I could optimize it.

number = int(input("Enter your number &gt;&gt; "))
print("\nCalculating...")
if number % 2 == 0: #Only even numbers
    primes = primenums(number) #returns all prime numbers &lt;= input number
    addend1 = primes[0]
    addend2 = primes[0]

    while addend1 + addend2 != number:
        if primes[-1] == addend2:
            addend2 = primes[primes.index(addend1) + 1]
            addend1 = primes[primes.index(addend1) + 1]
        else:
            addend2 = primes[primes.index(addend2) + 1]


Right now, up to 10,000 the algorithm is pretty fast, but at 100,000 it takes about 3 seconds to finish. Is that just how it is or could I make it faster?
One thing that makes your code slow is your repeated calls to primes.index. Each of these calls needs to linearly scan primes until it finds the value you are looking for, making this \$\mathcal{O}(n)\$. This is especially bad in the first if case since you do this twice with exactly the same argument. Instead just keep the index around in addition to the number:

def goldbach_keep_index(number):
    if number % 2 == 1: #Only even numbers
        raise ValueError("Goldbach conjecture is only defined for even numbers")
    primes = primenums(number) #returns all prime numbers &lt;= input number
    i, j = 0, 0
    addend1 = primes[i]
    addend2 = primes[j]

    while addend1 + addend2 != number:
        if addend2 == primes[-1]:
            i = j = i + 1
            addend2 = primes[i]
            addend1 = primes[i]
        else:
            j += 1
            addend2 = primes[j]
    return addend1, addend2


Note that I made this a function, so you can reuse it.

Your main calling code could look like this:

if __name__ == "__main__":
    number = int(input("Enter your number &gt;&gt; "))
    p1, p2 = goldbach_keep_index(number)
    print(f"{p1} + {p2} = {number}")




However, what you are really doing is taking all combinations of prime numbers, without repeating yourself. So just use itertools.combinations_with_replacement:

from itertools import combinations_with_replacement

def goldbach_combinations(number):
    if number % 2 == 0:
        raise ValueError("Goldbach conjecture is only defined for even numbers")
    primes = primenums(number)
    for addend1, addend2 in combinations_with_replacement(primes, 2):
        if addend1 + addend2 == number:
            return addend1, addend2
    raise Exception(f"Found a counter-example to the Goldbach conjecture: {number}")


In this case primes does not even need to be a list, it can just be a generator.



If you instead make primes a set, you can easily implement the idea suggested by @Josiah in their answer by just checking if number - p is in primes:

def goldbach_set(number):
    if number % 2 == 0: #Only even numbers
        raise ValueError("Goldbach conjecture is only defined for even numbers")
    primes = set(primenums(number)) #returns all prime numbers &lt;= input number
    for p in primes:
        k = number - p
        if k in primes:
            return p, k
    raise Exception(f"Found a counter-example to the Goldbach conjecture: {number}")




And now some timing comparisons, where goldbach is your code put into a function:

def goldbach(number):
    if number % 2 == 0: #Only even numbers
        raise ValueError("Goldbach conjecture is only defined for even numbers")
    primes = primenums(number) #returns all prime numbers &lt;= input number
    addend1 = primes[0]
    addend2 = primes[0]

    while addend1 + addend2 != number:
        if primes[-1] == addend2:
            addend2 = primes[primes.index(addend1) + 1]
            addend1 = primes[primes.index(addend1) + 1]
        else:
            addend2 = primes[primes.index(addend2) + 1]
    return addend1, addend2


And primenums is a simple sieve:

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 primenums(limit):
    return list(prime_sieve(limit))




And when pulling the generation of the primes outside of the function (and calculating them up to the largest number in the plot):



Of course the first three functions are vastly slower than the set because they need to go through more combinations now. However, all functions are then constant time, so the increase in time comes solely from the fact that you have to consider more primes.