[Project Euler] 50. Consecutive prime sum

1. 개요

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

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

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

2. 구현

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

# -*- 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이다.