Golbach's Conjecture - Brute force

"""
Agenda:

    Test Golbach's conjecture for all even numbers up to N


Algorithm:

    for every even number n up to N:
        for every prime number a less than n / 2:
            b = n - a
            if b is prime:
                next n
            else:
                next a
        else:
            print n
            Conjecture False!
"""


def get_primes(upper):
    '''Return a list of primes less than upper.'''
    nums = range(3, upper, 2)
    p = 3
    x = 0 # nums[x] == p
    stop = pow(upper, 0.5)
    nums_end = len(nums)
    while p <= stop:
        for m in xrange(x+p, nums_end, p):
            nums[m] = 0
        while True:
            x += 1
            if nums[x]:
                p = nums[x]
                break
    return [2] + [n for n in nums if n]


def get_input_N():
    '''Handle user input and return N as int.'''
    print "Test the Golbach conjecture for all even numbers up to N"
    while True:
        try:
            N = int(raw_input('N='))
            if N > 10**6:
                print "That many? Sit back, this is gonna take a while!"
            return N
        except ValueError:
            print "N can only be an integer!"


def main():
    N = get_input_N()
    primes_list = get_primes(N)
    primes_set = set(primes_list)
    for n in xrange(4, N + 1, 2):
        end = n / 2
        disproved = True
        for a in primes_list:
            if a > end:
                break
            b = n - a
            if b in primes_set:
                disproved = False
                break
        if disproved:
            print n, "disproves Golbach's conjecture"
##            break


if __name__ == '__main__':
    while True: main()