Home › Blogs › garrett's blog ›

Project Euler Problem 50

garrett // Nov 11, 2010
//

I wrote a bunch of these but never posted them up, so I'm just uploading them in bulk now. Not much to say about them at this point.

  1. #!/usr/bin/python
  2.  
  3. import Crypto.Util.number
  4.  
  5. def primes(n):
  6.   """ returns a list of prime numbers from 2 to < n """
  7.   if n < 2:  return []
  8.   if n == 2: return [2]
  9.   # do only odd numbers starting at 3
  10.   s = range(3, n, 2)
  11.   # n**0.5 may be slightly faster than math.sqrt(n)
  12.   mroot = n ** 0.5
  13.   half = len(s)
  14.   i = 0
  15.   m = 3
  16.   while m <= mroot:
  17.     if s[i]:
  18.       j = (m * m - 3)//2
  19.       s[j] = 0
  20.       while j < half:
  21.         s[j] = 0
  22.         j += m
  23.     i = i + 1
  24.     m = 2 * i + 3
  25.   # make exception for 2
  26.   return [2]+[x for x in s if x]
  27.  
  28. primes_list = primes(4000)
  29. print primes_list
  30. max_len = 0
  31. max_sum = 0
  32. primes_len = len(primes_list)
  33. for i1 in range(primes_len):
  34.     for i2 in range(i1+1, primes_len):
  35.         my_len = i2-i1
  36.         if my_len > max_len:
  37.             my_sum = sum(primes_list[i1:i2])
  38.             if my_sum < 1000000:
  39.                 if Crypto.Util.number.isPrime(long(my_sum)):
  40.                     max_len = my_len
  41.                     max_sum = my_sum
  42.        
  43. print max_sum