BOJ 1644: 소수의 연속합

#BOJ 1644: 소수의 연속합

1644번: 소수의 연속합

#풀이

n의 숫자를 연속된 소수의 합의 쌍을 구하는 문제이다.

 

일단 n까지의 소수를 구하여 배열에 집어 넣고

 

소수는 에라토스테네스의 체 알고리즘을 사용하여 구한다.

 

그리고 투 포인트를 사용하여 

 

구할 수 있다.

num은 지금까지 소수들의 연속합

 

조건

1. num < n

2. num > n

3. num == n

 

3가지의 상황에서 두 개의 포인터를 어떻게 할건지 정한다.

 

1. num < n

에서는 연속되는 다음 소수를 더해야한다.

2. num > n

크므로 맨 처음 더했던 소수를 뺀다.

3. num == n 

같으니까 맨 처음 더했던 소수를 빼고 다음 연속된 소수의 합을 찾는다.

 

#코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int n;
int num;
bool arr[4000001];
int ans;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	
	arr[1] = 1;
	for (int i = 2; i * i <= n; i++) {
		if (arr[i]) continue;
		for (int j = i * i; j <= n; j = j + i) {
			arr[j] = 1;
		}
	}
	vector<int> v;
	for (int i = 2; i <= n; i++) {
		if (!arr[i])
			v.push_back(i);
	}
	int st = 0;
	int en = 0;

	if (v.size() > 0) {
		while (st < v.size() && en < v.size()) {
			if (num == n) {
				num = num - v[st];
				st++;
				ans++;
			}
			else if (num < n) {
				num = num + v[en];
				en++;

			}
			else if (num > n) {
				num = num - v[st];
				st++;
			}
		}
		if (v[v.size() - 1] == n)
			ans++;
	}
	cout << ans << '\n';

	return 0;
}