Advertisement
russ123

Golbach's Conjecture - Brute force

Jun 27th, 2013
96
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.73 KB | None
  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()
Advertisement
RAW Paste Data Copied
Advertisement