이 목록의 모든 연속 하위 집합을 확인 했습니까?

Question

Project Euler에서 문제 50을 해결하려고합니다. 나에게 대답을주지 않거나 나를 위해 해결하지 말고,이 특정한 질문에 대답하려고 노력하십시오.

목표는 1 백만 이하의 소수에 덧붙인 연속 소수의 가장 긴 합을 찾는 것입니다. 나는 n보다 아래의 모든 소수를 찾기 위해 체를 썼다. 그리고 나는 그것이 옳았다는 것을 확인했다. 다음 방법을 사용하여 연속 소수의 각 하위 집합 합계를 확인하려고합니다.

빈 목록 sums이 있습니다. 각 소수에 대해 sums의 각 요소에 추가하고 새 합계를 확인한 다음 소수를 sums에 추가합니다.

가 여기 파이썬에

나는 문제가 소수가 있다고 말한다 백만

아래 두 개 이상의 연속 소수의 모든 합계 check()라고 한 경우 알고 싶은

primes = allPrimesBelow(1000000) 
sums = [] 
for p in primes: 
    for i in range(len(sums)): 
     sums[i] += p 
     check(sums[i]) 
    sums.append(p) 

, 953, 그것은 21 개의 연속 소수의 합으로 쓰여질 수 있지만, 나는 그것을 발견하지 못한다.

Answer 1

코드가 정확합니다. 나는 그것을 실행했고 953이라는 숫자를 생성했기 때문에 문제는 아마도 프라임 생성 함수와 관련이있다. 백만 분의 밑에 ​​78498 소수가 있어야합니다 - 당신은 그 결과를 얻는 지 확인하고 싶을 수도 있습니다.

즉, check()가 3,080,928,753 번 호출되므로 코드 실행에 오랜 시간이 걸릴 것이라고합니다. 적은 금액을 확인하는 메소드를 찾고 싶을 수 있습니다. 나는 당신이 스포일러를 요구하지 않았기 때문에 이것을 확장하지 않을 것이지만, 일반적인 힌트에 관심이 있다면 알려주십시오.

Answer 2

나는 내 머리 꼭대기에서 곧바로 답을 찾지 못했지만, 중첩 된 배열로 합을 만들고 나서 합계 카운터에 소수점을 추가하는 대신 서브 배열에 소수점 p를 추가 했습니까? 그러면 각 하위 배열에 어떤 소수가 추가되었는지 시각적으로 확인할 수있게되며 확장으로 원래 코드가 합쳐진 소수를 알 수 있습니다.