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

백준 1644 소수의 연속합 문제
백준 1644 소수의 연속합 소스코드

📄 문제 설명

Problem

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

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과 같은 표현도 적합하지 않다.

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

Input

첫째 줄 : 자연수 N (1 ≤ N ≤ 4,000,000)

Output

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

Example Input 1

20

Example Output 1

0

Example Input 2

3

Example Output 2

1

Example Input 3

41

Example Output 3

2

Example Input 4

53

Example Output 4

2

📝 문제 해설

이 문제는 자연수 N을 연속된 소수의 합으로 나타나는 case 경우의 수를 출력하는 프로그램으로,
소수찾는 알고리즘인 <에라토스테네스의 체>와 <누적합>, <투포인터>를 활용할 것이다.

※ 소수 (Prime Number) : 약수로 1과 자기 자신만을 가지는 정수

▶ 에라토스테네스의 체 (소수 찾기)

ⓐ 2부터 소수 판정을 시작한다.
ⓑ 판정하려는 수가 소수로 제외된 수가 아니고,
ⓒ 그 수의 약수가 1과 자기자신 뿐인 소수라면 그 수의 배수를 모두 제외시킨다.
  (원하는 수까지 진행 반복)

에라토스테네스의 체 : 위키백과

소수를 구한 후에 소수를 더한 누적합 배열(sum)과
앞부터 탐색하는 포인터(pt1)와 뒤부터 탐색하는 포인터(pt2)를 생성한다.

pt1부터 pt2까지의 합 sum[pt2] - sum[pt1]이
ⓐ 원하는 값(n)보다 클 경우 pt2--;
ⓑ n보다 작을 경우 pt1++;
ⓒ 같을 경우 result++; pt1++;

⚠ 주의할 점은 누적합 배열 sum 생성시 0을 추가해주어야한다.
n 자체가 소수일 수 있으므로 소수 하나도 연속된 수이기 때문이다.

예를 들어)
53은: 5+7+11+13+17 인 경우도 가능하지만, 53 그 자체로도 가능하다!

</> Source Code

#include <bits/stdc++.h>
#define MAX 4000010

using namespace std;

int main() {
	int n;
	scanf("%d", &n);

	// setPrime
	vector<int> prime;
	bool isPrime[MAX];
	
	for (int i = 0; i < MAX; i++) {
		isPrime[i] = true;
	}

	for (int i = 2; i < MAX; i++) {
		if (isPrime[i]) {
			prime.push_back(i);
			for(int j = 2 * i; j < MAX; j += i) {
				isPrime[j] = false;
			}
		}
	}

	// 누적합 구하기
	vector<int> sum;
	int total = 0;
	
	sum.push_back(0);
	for(int i = 0; i < prime.size(); i++) {
		total += prime[i];
		sum.push_back(total);
	}

	int pt1 = 0, pt2 = 0;
	int result = 0;

	// two pointer : pt1 - pt2
	while ((pt2 <= pt1) && (pt1 < sum.size())) {
		int sub = sum[pt1] - sum[pt2];
		if (sub == n) {
			result++;
			pt1++;
		}
		else if (sub < n) {
			pt1++;
		}
		else {
			pt2++;
		}
	}

	printf("%d", result);

	return 0;
}