[백준] 소수의 연속합 (1644번)

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

---

백준 부분합 (1806번) 문제의 진화버전인, 소수의 연속합이다.

부분합 문제에서 크게 벗어나진 않고, 구하는 게 배열의 길이가 아닌 가능한 배열의 수라는 점과,

배열이 주어지지 않고 소수인 연속 배열이라는 점이다.

 

소수가 나오면 일단 에라토스테네스의 체를 사용해야한다. 

소수를 구하고, 판별하는 크게 어렵지 않은 개념이니 한 번 공부해두면 두고두고 유용하게 쓴다.

우선 에라토스테네스의 체로 소수를 판별한다.

이 때해결방법은 배열을 새로 만들어서 소수들만 넣는 방법과, 그냥 기존 배열 그대로 진행하는 법이 있는데, 

난 번거로워서 소수를 판별하는 isPrime 배열을 그대로 사용했다.

 

다음부턴 부분합과 비슷하게 투 포인터를 이용해서 가능한 소수의 연속합의 수를 구한다.

합이 N보다 작으면 hi를 다음 소수까지 증가시킨 후 sum에 더한다.

합이 N보다 크거나 같으면 lo를 sum에서 뺀 후, lo를 다음 소수까지 증가한다. 

while이 끝날때까지 수행하면 가능한 모든 개수를 구할 수 있다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%86%8C%EC%88%98%EC%9D%98%20%EC%97%B0%EC%86%8D%ED%95%A9%20(1644%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
using namespace std;
bool isPrime[4000001];
int N;

void eratos() {
	memset(isPrime, true, sizeof(isPrime));
	isPrime[1] = false;
	for (int i = 2; i*i <= 4000000; i++) {
		if (!isPrime[i]) continue;
		for (int j = i + i; j <= 4000000; j += i) {
			isPrime[j] = false;
		}
	}
}

int main()
{
	
	eratos();

	cin >> N;

	int lo = 2;
	int hi = 2;
	int sum = 2;
	int res = 0;

	while (lo <= hi && hi <= N) {
		if (sum < N) {
			hi++;
			while (!isPrime[hi])
				hi++;
			sum += hi;
		}
		else if (sum == N) {
			res++;
			sum -= lo;
			lo++;
			while (!isPrime[lo])
				lo++;
		}
		else if(sum > N) {
			sum -= lo;
			lo++;
			while (!isPrime[lo])
				lo++;
		}
	}

	cout << res;
}