[3] 소수의 합

Programmers 문제 - 소수의 합

[시간제한]

모든 테스트 케이스를 합쳐 1초

[메모리제한]
512MB

[문제]

2부터 N까지의 모든 소수의 합을 구하세요. N이 7이라면 {2,3,5,7} = 17을 출력 하시면 됩니다.

N의 범위는 2이상 10,000,000이하 입니다. 효율성 테스트의 모든 시간 제한은 1초입니다.

=======================================================================

[Idea]

방법 1) O(n^2)로 다 돌려서 확인하는 경우

: 기존의 소수를 구하는 방법이다. 이 방법은 n^2으로 시간복잡도가 안좋다. 효율성 4개 다 틀림

방법 2) O(n^2)로 다 돌려서 확인하는 경우2

1과 똑같은 원리이지만 시간을 줄이기 위해 이중for문 내 나누는 연산자의 범위를 2~√n 까지만 돌린다. 

약수가 있는지 확인하면 되기 때문에 √n 까지만 해주어도 결과는 동일하고 시간은 비교적 줄어든다. 이 방법은 효율성 4개중 1개만 맞았다.

방법 3) 에라토스테네스의 채를 활용하는 방법 ==> O(nloglogn)

생각외로 간단하다. 배열을 만들어 해당 idx의 값이 0이면 소수로 찍어내고, 이후의 배수들은 범위까지 2씩를 곱하여 1로 체크해주는 것이다. 아래 gif를 보면 이해가 편할 것이다. 

이 방법이 빠를 까라는 의문이 들었는데 해보니 효율성이 다 맞았다. 코드도 위 2방법보다 짧았다.....ㄷㄷ

출처 : http://www.xn--299as6vb5i1je.com/interview/36