Problem 10. 2백만 이하 소수들의 합

Project Euler - Problem 10.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

- 10 이하의 소수들의 합은 2+3+5+7 = 17이다. 그렇다면 200만 이하의 소수들의 합은?

이런 식으로 구할 수 있습니다.

하지만, 100만개의 루프(짝수 제외)를 돌아야하기 때문에 해가 나오길 꽤나 오랜시간 기다려야합니다.

- 저도 못기다려서 실행중에 껐습니다.

연속된 소수를 구하는 방법에는 에라토스테네스의 체 라는 방법이 있습니다.

에라토스테네스의 체

소수를 구하는 방법으로 조금만 생각해보면 유추해낼 수 있는 방법입니다.

1. 1은 소수가 아니므로 제외합니다.

2. 2는 소수이기 때문에 포함시키고 2의 배수를 모두 제거합니다.

3. 3은 소수이기 때문에 포함시키고 3의 배수를 모두 제거합니다.

4. 5는 소수이기 때문에 포함시키고 5의 배수를 모두 제거합니다.

5. 7은 소수이기 때문에 포함시키고 7의 배수를 모두 제거합니다.

6. 이와 같은 과정을 계속 반복하면 원하는 구간의 소수들만 남게 됩니다.