BaekJoon(1644)::소수의 연속합

문제

1644번: 소수의 연속합

문제파악

연속된 소수의 합으로 나타낼수 있는지 여부의 문제이다.

다면 여기서 연속된 소수의 합이기 떄문에 소수판별의 문제와 투포인터를 사용해서 문제를 풀수 있을 것으로 보인다

문제풀이

1. 소수판별(에라토스테네스의 체)
2. 투포인터

2가지를 고려해서 'r_index까지의 합'에서 'l_index까지의 합'을 뺌으로써 값을 찾을 수 있다

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

const int MAX_N = 4000000;

vector<int> primSumArr;
bool primeArrYn[MAX_N + 1];

void setSieveOfEratosthenes() {						
	memset(primeArrYn, true, sizeof(primeArrYn));
	primeArrYn[0] = false;
	primeArrYn[1] = false;

	for (int i = 2; i < sqrt(MAX_N + 1); i++) {
		if (!primeArrYn[i]) continue;

		for (int idx = i * 2; idx <= MAX_N; idx += i) {
			primeArrYn[idx] = false;
		}
	}

	int sum = 0;
	primSumArr.push_back(sum);
	for (int i = 0;i <= MAX_N;i++) {
		if (primeArrYn[i]) {
			sum += i;
			primSumArr.push_back(sum);
		}
	}
}

int main() {
	setSieveOfEratosthenes();
	int target;
	bool findYn = false;
	int cnt = 0;
	cin >> target;

	int l_index = 0;
	int r_index = 0;
	
	while (r_index < primSumArr.size()) {
		int subSum = primSumArr[r_index] - primSumArr[l_index];

		if (subSum < target) {
			r_index++;
		}
		else if(subSum > target) {
			l_index++;
		} else {
			cnt++;
			r_index++;
		}

	}

	cout << cnt << endl;

	return 0;
}