# Golbach's Conjecture - Brute force

Jun 27th, 2013
96
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. """
2. Agenda:
3.
4.    Test Golbach's conjecture for all even numbers up to N
5.
6.
7. Algorithm:
8.
9.    for every even number n up to N:
10.        for every prime number a less than n / 2:
11.            b = n - a
12.            if b is prime:
13.                next n
14.            else:
15.                next a
16.        else:
17.            print n
18.            Conjecture False!
19. """
20.
21.
22. def get_primes(upper):
23.     '''Return a list of primes less than upper.'''
24.     nums = range(3, upper, 2)
25.     p = 3
26.     x = 0 # nums[x] == p
27.     stop = pow(upper, 0.5)
28.     nums_end = len(nums)
29.     while p <= stop:
30.         for m in xrange(x+p, nums_end, p):
31.             nums[m] = 0
32.         while True:
33.             x += 1
34.             if nums[x]:
35.                 p = nums[x]
36.                 break
37.     return [2] + [n for n in nums if n]
38.
39.
40. def get_input_N():
41.     '''Handle user input and return N as int.'''
42.     print "Test the Golbach conjecture for all even numbers up to N"
43.     while True:
44.         try:
45.             N = int(raw_input('N='))
46.             if N > 10**6:
47.                 print "That many? Sit back, this is gonna take a while!"
48.             return N
49.         except ValueError:
50.             print "N can only be an integer!"
51.
52.
53. def main():
54.     N = get_input_N()
55.     primes_list = get_primes(N)
56.     primes_set = set(primes_list)
57.     for n in xrange(4, N + 1, 2):
58.         end = n / 2
59.         disproved = True
60.         for a in primes_list:
61.             if a > end:
62.                 break
63.             b = n - a
64.             if b in primes_set:
65.                 disproved = False
66.                 break
67.         if disproved:
68.             print n, "disproves Golbach's conjecture"
69. ##            break
70.
71.
72. if __name__ == '__main__':
73.     while True: main()