[알고리즘] 소수의 연속합

구현 방식

• 소수를 구할 때는 에라토스테네스 체 알고리즘을 이용한다.
• 구간 합을 구할 때는 두 포인터 알고리즘을 이용한다.
• 현재 값이 N 보다 작으면 큰값을 더 하고, 크면 작은 값을 빼면서 탐색.
• 원래는 partialSumCount를 구할 때 아래와 같이 while 문 분기문에서 사이즈 체크를 해서 넘어가려고 했으나, 끝 포인터는 이미 오버되었지만, 시작 포인터가 앞에서 한칸 한칸 오고 있는 경우를 생각하지 못하게 되므로, 체크 구간을 중간에 넣어주었다.

while (endIdx < primes.size()) // 이렇게되면 startIdx 만 1씩 증가시키고 있는 경우는 탐색 불가
{
	if (N <= sum)
		sum -= primes[startIdx++];
	else
		sum += primes[endIdx++];

	if (sum == N)
		counter++;
}

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

vector<int> primes;

void solution(int N) 
{
	calcEratos(N);
	cout << partialSumCount(N);
}

void calcEratos(int N)
{
	if (N <= 1) return;

	vector<bool> numbers(N + 1, true);

	for (int i = 2; i * i <= N; i++)
	{
		if (numbers[i])
			for (int j = i * i; j <= N; j += i)
				numbers[j] = false;
	}

	for (int i = 2; i <= N; i++)
	{
		if (numbers[i]) primes.push_back(i);
	}

	return;
}


int partialSumCount(int N)
{
	int counter = 0;
	int startIdx = 0, endIdx = 0, sum = 0;

	while (true)
	{
		if (N <= sum)
			sum -= primes[startIdx++];
		else if (primes.size() <= endIdx)
			break;
		else
			sum += primes[endIdx++];

		if (sum == N)
			counter++;
	}
	return counter;
}