백준1644 - 소수의 연속합

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

1644번: 소수의 연속합

에라토스테네스의 체와 구간 합 알고리즘을 합친 문제다. n이하의 소수를 모두 구하여 연속된 소수의 합이 n이 되는 순간 경우의 수를 증가시키면 된다. 구간합 알고리즘은 셩님블로그를 참고하였다.

 

ex1.)입력이 24인 경우

2 3 5 7 11 13 17 19 23 : 24이하 소수의 갯수는 9, 따라서 r은 9이면 탈출

24이면
2 -> 2
2 3 -> 5
2 3 5 -> 10
2 3 5 7 -> 17
2 3 5 7 11 -> 28
3 5 7 11 -> 26
5 7 11 -> 23
5 7 11 13 -> 36
7 11 13 -> 31
11 13 -> 24
13 -> 13
13 17 -> 30
17 -> 17
17 19 -> 36
19 -> 19
19 23 -> 42
23 -> 23, r = 9라서 마지막이라 탈출

  

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

int mat[4000001];
int n;
int cnt = 0, sum = 0, l = 0, r = 0;
vector<int> v;

//소수 찾기 알고리즘, n이하인 모든 소수를 찾는다.
void Prime() {
	//모든 수를 자기자신으로 초기화
	for (int i = 1; i <= n; i++) {
		mat[i] = i;
	}
	for (int i = 2; i <= n; i++) {
		if (!mat[i]) { //소수가 아니면
			continue; //건너뛴다.
		}
		for (int j = i + i; j <= n; j += i) { //현재 i에 2 * i를 한 수부터 소수를 찾는다.
			mat[j] = 0; //소수가 아니니까 0으로 만든다.
		}
	}

	//소수가 아니면 벡터에 삽입
	for (int i = 2; i <= n; i++) {
		if (mat[i]) { 
			v.push_back(mat[i]);
		}
	}
}

int main() {
	cin >> n;
	
	Prime(); //소수 찾기 알고리즘

	//구간 합 알고리즘, 연속된 수의 특정 구간 합을 구할 때 사용
	//l과 r사이의 구간합 구하기
	//구간 합이 n보다 크면 현재 l위치에 있는 수를 뺀다.
	//구간 합이 n보다 작으면 현재 r위치에 있는 수를 더한다.
	while (1) {
		if (sum >= n) {
			sum = sum - v[l];
			l++;
		}
		else if (r == v.size()) {
			break;
		}
		else {
			sum = sum + v[r];
			r++;
		}

		if (sum == n) {
			cnt++;
		}
	}

	cout << cnt;
}