Problem

2부터 N까지의 모든 소수의 합을 구하세요. N의 범위는 2 ≤ N ≤ 10,000,000 시간 제한은 1초입니다.

Tip

소수란 1과 자기자신을 제외한 어떤 자연수로도 나누어 떨어지지 않는 (나머지가 0이 되지 않는) 2이상의 자연수를 말합니다. 일반적인 방법으로 나머지 연산인 % (Moduler)를 이용해 2부터 (자기자신 - 1) 까지 나머지를 비교하는 것으로 소수를 찾을 수 있습니다.

또한, N의 제곱근 만큼만 비교를 하는 것으로도 소수를 판별할 수 있습니다.

100의 약수는 1,2,4,5,10,20,25,50,100 이고, 100의 제곱근은 10입니다. 10을 기준으로 좌우 대칭되는 값, 1,100, 2,50, 4,25, 5,20이 쌍을 이루고 있습니다. 대칭되는 약수 쌍의 왼쪽을 a, 오른쪽을 b 라고 한다면 a x b = 100입니다. N의 약수가 있다면 루트 N을 기준으로 좌우 대칭이므로 a가 발견되면 자연스럽게 b가 존재한다는 것을 유추할 수 있습니다. 반대로 생각하면 a를 찾지 못하면 a x b = 100을 만족하는 b 또한 찾을 수 없습니다. (소수)

하지만, 문제에서 이 방식으로 접근하면 실행시간을 초과하게 됩니다. N의 크기가 1천만이라는 큰 수 일수도 있기 때문인데요. 문제는 모든 소수의 합을 구해야 하는데, 1천만이 소수인지 판별하는 것만 해도 3~4만번 연산을 수행해야 합니다. 따라서, 이 방법으로는 실행시간을 맞추기는 어려워 보입니다. 그렇다면 어떻게 실행시간을 맞출 수 있을까요?

HINT : 소수의 배수는 소수가 아닙니다.

Solving

에라토스테네스의 체

출처 : wikipedia

위 그림은 소수 판별법 중 하나인 에라토스테네스의 체의 알고리즘을 표현한 그림입니다. 소수의 배수는 소수가 아니라는 점을 이용합니다.

소수가 아닌 수를 거르는 거대한 그물을 생각해보세요. 처음에 모든 수를 소수로 보고 아무것도 거르지 않습니다. (0, 1 제외) 가장 작은 소수인 2부터 시작하여 2의 배수를 걸러줍니다. 모두 걸렀다면 그물에는 2의배수는 남아있지 않게됩니다. 그다음 2의 배수에 걸리지 않은 3은 소수로 보고 3의 배수를 모두 걸러줍니다. 그러면, 그물에는 3의 배수 또한 남아있지 않게 됩니다. 이렇게 계속 진행하다 보면 그물에는 어떠한 수에도 걸러지지 않은 수들이 남아있게 되고, 이 수들을 소수로 볼 수 있습니다. 어떤 수에도 걸러지지 않았다는 것은 어떤 수의 배수도 아니라는 의미입니다.

구현의 관점으로 보겠습니다. N의 범위가 2 ≤ N ≤ 10,000,000 이므로 넉넉하게 배열의 범위를 1천만 + 1 정도로 잡아줍니다. 이 배열은 그물에 해당합니다. 저의 경우 생각하기 쉽게 isPrime으로 작명하고 초기화를 진행했는데, 이를 isNotPrime으로 보고 초기화 작업을 따로 진행하지 않으셔도 됩니다. 정답이 소수의 합이므로 int형의 범위를 넘을 수도 있어서 long long형으로 받아 계산했습니다.

배열을 2부터 N까지 돌면서 만일 해당 값이 소수이면 (아무도 건들지 않았다면) 해당수의 배수를 모두 false값으로 바꾸어 소수가 아니라는 것을 표기해 줍니다. loop를 돌면서 소수인 수는 answer값에 더해줍니다. loop를 탈출했다면 answer를 반환하여 정답을 출력합니다.

Code

C++로 풀이한 참고용 코드입니다.

Github

#include <iostream>

using namespace std;

bool isPrime[10000001];

int main() {
	long long answer = 0;
	int N;

	cin >> N;

	for (int i = 2; i <= N;i++) {
		isPrime[i] = true;
	}

	for (int i = 2; i <= N; i++) {
		if (isPrime[i]) {
			answer += i;
			for (int j = i * 2; j <= N; j += i) {
				isPrime[j] = false;
			}
		}
	}

	cout << answer;

	return 0;
}