[1644번] 소수의 연속합

www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

문제를 해결하기 위해 할 일

 

첫 번째. 소수 구하기

 

소수를 구하기 위해 에라토스테네스의 체 사용

 

자신의 배수를 미리 제거하여 연산의 횟수를 줄인다.

 

memset(arr, true, sizeof(arr));

arr[1] = false;

for (int i = 1; i <= 4000005; i++) {
	if (arr[i] == true) {
		for (int k = 2; i * k < 4000005; k++) {
			arr[i * k] = false;
		}
	}
}

 

두 번째. 구한 소수를 배열에 넣기

 

에라토스테네스의 체를 사용하여 구한 소수(arr배열의 원소가 true일 경우)를 탐색할 배열에 넣는다.

 

vector<int> v;

for (int i = 2; i <= 4000005; i++) {
	if (arr[i] == true) {
		v.push_back(i);
	}
}

 

세 번째. 투 포인터를 이용하여 연속합을 구한다

 

start와 end를 이용하여 위에서 선언한 소수 배열을 탐색한다.

- start = 더하기 연산을 시작할 위치

- end = 더하기 연산이 끝나는 위치

end 인덱스의 값은 계속 더하고 start 인덱스의 값은 빼면서 배열 전체를 탐색할 수 있다.

 

소수의 합과 입력한 N과의 관계

i) 소수의 합 >= N --> 소수의 합에서 소수 배열의 start 번째 값을 뺀다.

ii) 소수의 합 < N --> 소수의 합에서 소수 배열의 end 번째 값을 더한다.

 

이때, 소수의 합과 N이 같으면 경우의 수를 하나 찾은 것으로 간주한다.

 

int sum = 0;
int start = 0;
int end = 0;
int cnt = 0;

while (1) {
	if (sum >= n) sum -= v[start++];
    // end의 값이 소수 배열의 크기와 같거나 소수 배열의 값이 N보다 클 때
	else if (end == v.size() || n < v[end]) break; 
	else sum += v[end++];
	if (sum == n) cnt++;
}

 

전체 코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

bool arr[4000008];

int main() {
	
	int n;
	cin >> n;

	memset(arr, true, sizeof(arr));

	arr[1] = false;

	for (int i = 1; i <= 4000005; i++) {
		if (arr[i] == true) {
			for (int k = 2; i * k < 4000005; k++) {
				arr[i * k] = false;
			}
		}
	}

	vector<int> v;

	for (int i = 2; i <= 4000005; i++) {
		if (arr[i] == true) {
			v.push_back(i);
		}
	}

	int sum = 0;
	int start = 0;
	int end = 0;
	int cnt = 0;

	while (1) {
		if (sum >= n) sum -= v[start++];
		else if (end == v.size() || n < v[end]) break;
		else sum += v[end++];
		if (sum == n) cnt++;
	}

	cout << cnt << endl;

	return 0;
}