백준 1644 _ 소수의 연속합

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

1644번: 소수의 연속합

---

⭐ 내 소스 코드

#include<iostream>
#include<vector>
using namespace std;


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int num,count=0,sum=0;
	cin >> num;
	vector<int>vec;
    
	for (int i = 1; i <= num; i++) {
		vec.push_back(i);
	}
    
	vec[0] = 0;
    
    //소수 구하기
	for (int i = 2; i <= num; i++) {
		if (vec[i - 1] == 0) continue;
		for (int j = 2; j*i <= num; j++) {
			vec[j*i - 1] = 0;
		}
	}

	//연속된 소수들의 합 구하기
	for (int i = 0; i < vec.size(); i++) {
		if (vec[i] == 0) continue;
		for (int j = i; sum <= num; j++) {
			if (j < vec.size()) {
				if (vec[j] != 0) {
					sum += vec[j];
					if (sum == num) {
						count++;
						break;
					}
				}
			}
			else break;
		}
		sum = 0;
	}
	cout << count;
	
	return 0;
}

 

🙏 문제 풀이

#연속된 소수들의 합 구하기

• i는 덧셈을 시작할 소수를 지정
• j는 i부터 시작하여 소수들의 합계가 num 보다 커지기 전까지 소수들을 차례대로 더한다
• 더한 소수의 합이 num과 같아질 경우 경우의 수를 증가시켜준다
• 더한 소수의 합이 num보다 커질 경우, 합계를 0으로 초기화하고 그다음 소수부터 차례대로 더해본다