BOJ 1644 - 소수의 연속합

1644번: 소수의 연속합 (acmicpc.net)

 

접근 방법

투 포인터와 소수판별 알고리즘이 혼합된 문제이다.

소수 판별을 하기 위해 에라스토테네스의 체를 이용하여 소수를 배열에 저장한다.

해당 소수 배열을 투포인트를 돌면서 각 연속적인 수들의 합이 N이 될 때, 경우의 수를 + 1한다.

 

코드

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

#define MAX 4000001
#define ll long long

bool chk[MAX+3];
vector<ll> arr;
ll n, s;

void func() {
	chk[1] = true;
	for (int i = 2; i < MAX; i++) {
		if(!chk[i])
			arr.push_back(i);
		for (int j = i + i; j < MAX; j+=i) {
			chk[j] = true;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;

	func();
	int l = 0; int r = 0;
	int tmp = 0;
	int res = 0;
	for (l = 0; l < arr.size(); l++) {
		
		while (r < arr.size() && tmp < n) {
			tmp += arr[r];
			r++;
		}

		if (tmp == n) {
			res++;
		}
		tmp -= arr[l];
	}
	cout << res;
}