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

문제

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

1644번: 소수의 연속합

 

문제이해

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

 

연속된 소수의 합으로 N을 나타낼 수 있는지 확인하기 위해서는 우선 2 ~ N 사이에 있는 소수를 찾아야 합니다. 에라토스테네스의 체를 사용하여 소수를 구한 다음 소수들을 연속으로 더해갑니다 만약 그 합이 N보다 작은 경우 계속 더해나가면 되고 N보다 작으면 앞에서 더했던 수를 빼기만 하면 됩니다. 만약 그 합이 N과 같으면 경우의 수를 +1 합니다.

 

다음은 해당 논리대로 구현된 코드입니다.

문제풀이

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

void sieve(vector<int>& P, int N) {
	for (int i{ 2 }; i * i <= N; i++) {
		if (P[i] == 1) {
			for (int a{ i * i }; a <= N; a += i) {
				P[a] = 0;
			}
		}
	}
	vector<int> T;
	for (int i{ 2 }; i < P.size(); i++) {
		if (P[i] == 1) {
			T.push_back(i);
		}
	}
	P = T;
}

int search(vector<int>& P, int sidx, int eidx, int target) {
	if (target == 2) {
		return 1;
	}
	int sum{ 0 };
	int times{ 0 };
	while (eidx < P.size()) {
		if (sum < target) {
			sum += P[eidx];
			eidx++;
		}
		else if (sum == target) {
			times++;
			sum += P[eidx];
			eidx++;
		}
		else {
			sum -= P[sidx];
			sidx++;
		}
	}
	while (eidx != sidx) {
		sum -= P[sidx];
		sidx++;
		if (sum == target) {
			times++;
		}
	}
	return times;
}

int main() {
	int N;
	cin >> N;
	vector<int> primes(N + 1, 1);
	sieve(primes, N);
	cout << search(primes, 0, 0, N);
}

void sieve

에라토스테네스의 체로 소수를 구한다음 그 소수들을 vector에 넣어주었습니다.

 

int search

연속된 소수의 합으로 N이 나오는 경우의 수를 찾는 함수입니다. sum의 값이 target보다 작을 경우 소수를 더해주고 같을 경우 times를 +1 했습니다. sum의 값이 target보다 클 경우에는 전에 더했던 소수를 빼는 방식으로 times(경우의 수)를 구했습니다.

 

문제후기

에라토스테네스의 체를 사용하기만 한다면 어렵지 않은 문제였습니다.