[C/C++] 백준 1644번 - 소수의 연속합

✏️ 문제 링크

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

1644번: 소수의 연속합

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

 

소수의 연속합을 구하는 문제입니다. 가장 먼저 소수는
에라토스테네스의 체알고리즘을 이용해서 구합니다. 그리고 구한 소수들을 vector에 추가해 줍니다.
그 후  합을 저장할 sum변수, 갯수를 셀 count변수 반복문 변수를 저장할 en을 선언했습니다.
먼저 vector의 크기만큼 for문을 돌려주고 그 안에서 계속 sum값을 0으로 초기화시킵니다. 그리고 나서 while반복문 안에서 en이 vector의 사이즈보다 작을 때까지 그리고 sum이 n보다 작을 때까지 돌리면서
sum==n일시 count값을 플러스해줍니다.

 

✏️ 문제 코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
int arr[4000005] = { 0,1 };
int n, m;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	vector<int>v;
	for (int x = 1; x <= sqrt(4000005); x++) {
		if (arr[x] != 0)
			continue;
		for (int y = x * x; y <= 4000005; y += x)
			arr[y] = 1;
	}
	for (int x = 2; x <= n; x++) {
		if (arr[x] == 0)
			v.push_back(x);
	}
	int en = 0, count = 0;
	int sum = 0;
	for (int st = 0; st < v.size(); st++) {
		sum = 0;
		en = st;
		while (en < v.size() && sum < n) {
			sum += v[en];
			if (sum == n)
				break;
			en++;
		}
		if (sum == n)
			count++;
	}
	cout << count;
}