본문 바로가기

오일러프로젝트

[오일러프로젝트] 50번문제


41은 소수이면서 다음과 같은 6개의 연속된 소수의 합으로도 나타낼 수 있습니다.

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

이것은 100 이하에서는 가장 길게 연속된 소수의 합으로 이루어진 소수입니다.

1000 이하에서는 953이 연속된 소수 21개의 합으로 가장 깁니다.

1백만 이하에서는 어떤 소수가 가장 길게 연속되는 소수의 합으로 표현될 수 있습니까?


이거 결국은 풀지못하고
풀이를 찾아본문제... 소수배열 만들어 놓고 for 2개로 돌리면 되기는 하는데
100만이하의 소수면 거의 끝나지도 않을 것 같고...해서 외국 블로거의 풀이를
보고 이를 분석하는 것으로 만족...ㅋ

1~100까지의 예를들면
소수배열 : [2,3,5,7,11,13,17,19,23,29,31...]
각 소수의 합 : [2,5,10,17,28,41,58,77,100]

1) index ~ n까지의 합은 sum(n) - prime_list[index]와 같다.

index ~ n까지의 최고 term을 가진 소수를 찾았으니 그다음은 n ~ 찾으면 된다.

를 바탕으로한 로직임



Python

Ruby
Perl