[마이다스챌린지2017예선] 소수합 문제

소수합 문제 (PrimeSum)

철수는 학교에서 처음으로 소수에 대한 개념을 배웠고, 다음과 같은 숙제를 하나 받아왔습니다.

“100부터 200 사이에 있는 모든 소수들의 합을 구하시오.”

철수는 100부터 200까지 일일이 숫자 하나 하나가 소수인지를 따져 모든 소수를 구한 뒤 합을 구했습니다. 숙제를 해결하고 난 뒤 철수는 담임 선생님이 비슷한 유형의 숙제를 반복적으로 낸다는 것을 깨달았습니다. 개념이 유사한 숙제를 반복적으로 하는 것이 싫어진 철수는 여러분에게 이런 문제를 계산해주는 프로그램을 만들어 달라고 요청했습니다.

두 숫자를 입력 받아, 그 사이에 존재하는 모든 소수들의 합을 구하는 프로그램을 작성하십시오.

입력

입력은 표준 입력(stdin)으로 주어지며

첫째 줄에는 M이, 둘째 줄에는 N이 각각 주어집니다.( 1 <= N, M <= 200,000 )

단, N은 M보다 크거나 같습니다.( M <= N )

출력

출력은 표준 출력(stdout)으로 이루어집니다.

M <= 소수 <= N 을 만족하는 모든 소수들의 합을 구하시오. 단, 소수가 아예 없는 경우 -1을 출력합니다.

입력예)

100

200

출력예)

3167

입력예)

200

205

출력예)

-1

#include <iostream>
#include <vector>
using namespace std;

vector<int> GetPrimes(int num) 
{
	int *arr = new int[num + 1];
	for (int i = 2; i <= num; i++)
		arr[i] = i;

	vector<int> retPrimes;
	for (int i = 2; i <= num; i++)	
	{
		if (arr[i] == 0)
			continue;

		for (int j = i + i; j <= num; j += i) {
			arr[j] = 0;
		}
	}

	for (int i = 2; i <= num; i++)
	{
		if (arr[i] != 0)
			retPrimes.push_back(arr[i]);
	}
	delete arr;
	return retPrimes;
}

int main()
{
	int N, M;
	cin >> N;
	cin >> M;
	vector<int> v = GetPrimes(M);

	int sum = 0;
	for (int vn : v)
	{
		if (vn >= N && vn <= M)
			sum += vn;
	}

	if (sum == 0)
		sum = -1;

	cout << sum;
	return 0;
}