[백준 C++] 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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

https://www.acmicpc.net/problem/1644

풀이

제한시간이 2초인점에서, N의 최댓값이 400만이므로, 400만이하의 모든 소수를 구해놔야, 연속된소수합(자기자신포함즉, 400만포함)을 계산할 수 있다.
여기서 일반적인 방법의 소수구하기알고리즘보다 에라토스테네스의 체 방법으로, 소수를 구해야했다.

참고 : https://marobiana.tistory.com/91
이 블로그내용을보아 5만가지일때 0.006초.. 아마 400만이면 충분히 1초안에 소수를 구할 수 있겠다.

이렇게 소수를 구한 소수는 deque에 담았다. 이는 400만까지의 소수를 구할때 vector를이용하면 메모리복사과정에 오버헤드가 늘어날것을 알기에.. 잦은삽입이일어나므로 선택했다.
이 소수리스트의 첫부분부터 끝부분까지 시작인덱스를 0번째 원소 부터 n번째 원소까지하여 차례대로 연속합을 구해 나가면 됬다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using namespace std;
//prime : 2부터 num까지 모든 숫자 기록
//primeList : 2부터 num까지의 소수 만 기록
deque<bool> prime; 
deque<int> primeList;

void findPrime(int num) {
	prime.push_back(false); //1, 2, 3, ... , num
	int cnt = num;
	while(cnt--)
		prime.push_back(true); //모든요소를 true로 초기화
	for (int i = 2; i * i <= num; i++) { //소수를찾음
		if (!prime[i]) continue;
		for (int j = i + i; j <= num; j += i) 
			//i를 제외한 i의배수들을 전부 소수가아님을check
			prime[j] = false;
	}
	for (int i = 2; i <= num; i++)
		if (prime[i]) primeList.push_back(i);
}

int find(int num) {
	int res = 0;
	for (int i = 0; i <= primeList.size(); i++) { //소수갯수만큼반복
		//i인덱스로 시작되는 소수(2,3,5,7...)를 탐색
		int j = i; //현재 탐색중인인덱스 (i, i+1, i+2...)
		int sum = 0;
		int primeCnt = primeList.size() - i; //소수리스트 최대길이만큼반복
		vector<int> temp;
		//i + (i+1) + (i+2)... 해서 연속소수의합이 소수가되는지확인
		while (primeCnt--) { 
			sum += primeList[j]; //소수의합을 기록
			temp.push_back(primeList[j]); //디버깅용
			if (num == sum) { //연속소수합이 소수가되는경우
				res++; //찾음+1
				sum = 0; //합초기화
				break;
			}
			else if (num < sum) { //소수합 소수를넘어선.. 오류난경우
				sum = 0; //합초기화
				break; //합이 더 커지면 끝
			}
			j++; //다음 인덱스 탐색
		}
		//여기로오면 다음 i+1번째를 시작인덱스로 찾으러감
	}
	return res;
}

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

	findPrime(N);
	printf("%d", find(N));

	return 0;
}