우주의 IT 소행성

주어진 범위 내에서 소수를 찾아, 그 소수들의 합과 최소값을 가지는 소수를 출력하는 문제이다.

에라토스테네스의 체 알고리즘을 이용하여 소수를 구해주면 된다.

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

1) 2부터 N까지 모든 자연수를 나열

2) 남은 수 중 아직 처리하지 않은 가장 작은 수 i를 찾는다.

3) 남은 수 중에서 i의 배수를 모두 제거한다.

4) 더이상 반복할 수 없을 때 까지 2, 3을 반복

시간 복잡도는 O(NloglogN)으로 선형 시간에 필적할 수준.

하지만 메모리를 많이 잡아먹는 단점이 있으니 잘 확인해보아야 한다.