[Project Euler] 50. Consecutive prime sum

1. 개요

  문제는 이곳에서 확인할 수 있다. 41은 다음과 같이 6개의 연속한 소수의 합으로 표현될 수 있다. 

$$41=2+3+5+7+11+13$$

  그리고 41은 100보다 작은 소수 중 가장 길게 연속하는 소수의 합이다. 이와 같은 특성을 가진 1000보다 작은 소는 953으로 21개의 연속하는 소수의 합이다. 문제의 목표는 가장 길게 연속하는 소수 들의 합으로 나타낼 수 있는  100만 이하의 소수를 찾는 것이다.

2. 구현

  소수는 에라스토테네의 체를 사용한다. 연속하는 소수의 합을 구하면서 찾아야 하는 범위에 길이와 합을  반영하여 속도를 높인다.

# -*- coding: utf-8 -*-

lim = 1000000
is_prime = bytearray([1])*(lim+1)
is_prime[0] = is_prime[1] = 0

for i in range(2,int(lim**0.5)+1):
	if is_prime[i]:
		m = lim//i-i+1
		is_prime[i**2::i] = bytearray([0])*m

prime_list = [p for p, is_p in enumerate(is_prime) if is_p]

max_h = 0
max_p = 0
min_h = 0

for i in range(0, len(prime_list)-1):
	
	for j in range(i+min_h, len(prime_list)):
		
		tmp_p = sum(prime_list[i:j])
		tmp_h = j-i

		if tmp_p > prime_list[-1]:
			min_h = max_h
			break
		
		if tmp_p in prime_list and max_h < tmp_h:
			max_h = tmp_h
			print(tmp_p, max_h)

  답은 997651이다.