[C++] G3 백준 1644 - 소수의 연속합 (클래스5)

1. 문제 링크

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

소요 시간 : 45분

시도 횟수 : 3

 

2. 문제 설명

난이도 : G3

사용 알고리즘 : 수학, 소수, 에라토스테네스의 체

적혀있는 그대로. 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력하면 됨 !

 

3. 풀이 방식 및 해결

우선 소수를 판별해야 하니 에라토스테네스의 체를 이용했고(여기서 반복 범위를 잘못 설정해서 런타임 에러난 건 안 비밀),

소수를 구하는 과정에서 각 소수까지의 누적합을 벡터에 저장했다.

이후 투포인터를 활용해서 카운팅

 

#include<iostream>
#include<vector>

using namespace std;

bool num[4000001];
vector<long long> sums;

void eratos(int n) {
	for (int i = 2; i<=n;i++) {
		if (!num[i]) {
			sums.push_back(sums.back() + i);
			for (int j = 2; i*j <= n; j++) {
				num[i*j] = true;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	if (n == 1) {
		cout << 0;
		return 0;
	}

	sums.push_back(0);
	eratos(n);
	
	int le = 0, ri = 1;
	int cnt = 0;
	while (ri < sums.size()) {
		long long tmp = sums[ri] - sums[le];
		if (tmp == n) {
			cnt++;
			le++;
			ri++;
		}
		else if (tmp < n) ri++;
		else le++;
	}
	cout << cnt;
}

 

<오늘의 TMI>
비내 며칠동안 세차게 내리더니 오늘은 햇볕이 쨍쩅하네요 앞으로 많이 더우려나?
넷플릭스로 모범택시 보는 중
봤던건데 기억이 가물가물해서 새로운 느낌