largest_1m_prime.py

from math import sqrt, ceil

def find_primes(n):
  primes = list(range(2, n+2))
  for c in range(ceil(sqrt(n))):
    pp = primes[c]
    if pp == -1:
      c += 1
      continue
    for i in range(c+1, len(primes)):
      if primes[i] == -1:
        continue
      if primes[i] % pp == 0:
        primes[i] = -1
    c += 1
  return [p for p in primes if p != -1]

tgt = 1000000
primes = find_primes(tgt)

def find_sequential_prime():
  start = 0
  
  # binary search to find longest sequence length
  
  idx = len(primes) // 2
  d = idx // 2
  
  while d > 1:
    if sum(primes[start:idx]) > tgt:
      idx -= d
    else:
      idx += d
    d //= 2
  
  end = idx  
  seq_len = end - start
  
  print("considering %d primes" % seq_len)

  while True:
    print("Checking seq_len of ", seq_len)
    for i in range(seq_len):
      if sum(primes[i:i+seq_len]) in primes[i+seq_len:]:
        return sum(primes[i:i+seq_len])
    seq_len -= 1
    if seq_len == 0:
      print("error")
      
find_sequential_prime()