BOJ 1644 소수의 연속합

www.acmicpc.net/problem/1644

1644번: 소수의 연속합

두 포인터를 활용한 재미있는 문제였다.

n을 입력받아서 소수 판정을 해주고 prime 배열에 넣어주고 두 포인터를 쓰면 된다.

 

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

const int MX = 4000001;
vector<bool> sieve;
vector<int> prime;
int s, e, sum, cnt;

void era(int n) {
	sieve.resize(n + 1, true);

	sieve[0] = sieve[1] = false;
	for (int i = 2; i * i <= n; i++) {
		if (sieve[i]) {
			for (int j = i * 2; j <= n; j += i) sieve[j] = false;
		}
	}
	for (int i = 2; i <= n; i++) {
		if (sieve[i]) prime.push_back(i);
	}
}

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

	era(n);
	while (1) {
		if (sum >= n) sum -= prime[s++];
		else if (e == prime.size()) break;
		else sum += prime[e++];
		if (sum == n) cnt++;
	}
	cout << cnt << endl;

	return 0;
}

 

주의해야 할 점은 배열의 인덱스를 잘못 건드리는 것이다. 

문제에서 소수 배열의 크기를 n까지만 잡아서 1시간은 고생한 것 같다.