(백준/ C++) 1644 - 소수의 연속 합

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

1644번: 소수의 연속합

문제 키워드

1. 연속된 소수의 합으로 나타낼 수 있는 자연수
2. 자기 자신이 소수 일 때도 카운트 

 

해결 방법 

1. 에라토스테네스의 체 알고리즘을 통해 N이하(N포함)의 소수를 찾아 Vector에 넣는다. 

2. vector의 size가 0이 아닐 경우 두개의 index(oneIdx, twoIdx)는 vector의 맨 앞 인덱스 0을 가진다. 

3 sum이 N보다 작으면 twoIdx를 클 경우 oneIdx를 증가시킨다. 

※ sum은 one과 two 사이의 vector의 합 

▼TwoIdx ▲ OneIdx

2 + 3 + 5 + 7

3 + 5 + 7

코드

#include<iostream>
#include<vector>
#include<memory.h>
using namespace std;

// --- 에라토스테네스 채 ---
// --- 연속된 소수의 합  ---

constexpr int limitedNumber = 4'000'000;
bool arr[limitedNumber];
vector<int> primeNumber;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N; cin >> N;
	
	memset(arr, true, sizeof(arr));
	
	arr[0] = arr[1] = false; 

	for (int i = 2; i <= N / 2; ++i) {
		for (int j = i + i; j <= N; j+=i) {
			arr[j] = false;
		}
	}
	
	for (int i = 2; i <= N; ++i)
	{
		if (arr[i])
		{
			primeNumber.emplace_back(i);
		}
	}
	int onePointIdx, twoPointIdx, counts = 0, sum = 0 ; 
	
	if (primeNumber.size() != 0)
	{
		onePointIdx = twoPointIdx = 0;
		sum = primeNumber[onePointIdx];
	}
	else
	{
		cout << "0";
		return 0;
	}

	while (onePointIdx <= twoPointIdx && twoPointIdx < primeNumber.size())
	{
		if (sum == N)
		{
			counts++;
			twoPointIdx++;
			if (twoPointIdx >= primeNumber.size())
				break;
			sum += primeNumber[twoPointIdx];
		}
		else if (sum < N)
		{
			twoPointIdx++;
			if (twoPointIdx >= primeNumber.size())
				break;
			sum += primeNumber[twoPointIdx];
		}
		else if (sum > N)
		{
			sum -= primeNumber[onePointIdx];
			onePointIdx++;
		}
	}

	cout << counts;
	return 0; 
}