Problem 10

문제출처 : http://euler.synap.co.kr/prob_detail.php?id=10

첨으로 오일러 문제들 중 정리하게 된 문제

이백만 이하의 소수들을 모두 더해 출력하는 문제이다

브루트 포스로 풀게 될 경우 약 14분 이라는 시간을 잡아먹게 되므로 시간적으로 비효율적인 방법이다.

이를 수학적으로 접근하게 되면 빨리 풀 수 있게 되는데 에라토스테네스의 체라는 방법을 이용할 수 있다.

기본적으로 그 방법에 대해 알고는 있지만 제대로 사용해본 적이 없어서 다른 블로그의 글을 통해서 제대로 이해할 수 있었다.

https://m.blog.naver.com/PostView.nhn?blogId=leejuesong&logNo=220398206365&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F

에라토스테네스 방법은 주어진 숫자 범위들을 반복하며 2의 배수들로 나누고 3의 배수들로 나누고 5의 배수들로 나누고..이런 과정을 반복해

남은 것들이 소수라는 것을 알 수 있는 방법이다.

코드적으로 옮길 때 쉽진 않지만

for (int i = 2; (i*i) <= n; i++) {

if (vecPrime[i]) {

for (int j = i*i; j <= n; j += i)

vecPrime[j] = false;

}

}

과 같이 i*i 를 함으로써 배수만큼 이동할 수 있고 j에선 j+= i 를 하여 i의 배수마다 체크를 할 수 있게 된다.

이 방법으로 푸니 54초 이내에 답이 나왔다. 이유는 true 인 것들만 체크해서 답을 구하니 시스템이 체크해야 될 값들이 확 줄었기 때문.

블로그에선 0.1 초만에 된다고 하는데 난 1분가까이 걸린 이유는 뭘까.. 아무튼 수학적으로 접근해서 프로그램을 작성하면

성능향상에 크게 기여할 수 있고 또 그러한 사고를 가지면서 문제에 접근하는게 중요하다고 느끼게 된 문제.