[4일차] 정수론 F - 1644: 소수의 연속합

골드 Ⅲ

 

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

int N, K;
bool isPrime[4000001];
vector<int> primes;

int main() {
	scanf("%d", &N);
	for (int i = 2; i <= N; i++) isPrime[i] = true;

	for (int i = 2; i <= N; i++) {
		if (!isPrime[i]) continue;
		primes.push_back(i);
		for (int j = i + i; j <= N; j += i) {
			if(!isPrime[j]) continue;
			isPrime[j] = false;
		}
	}

	int low = 0;
	int high = 0;
	int cnt = 0;
	int sum = 0;

	while (high <= primes.size()) {

		if (sum == N) {
			cnt++;
			sum -= primes[low++];
		}
		else if (sum > N) sum -= primes[low++];
		else {
			if (high == primes.size()) break;
			sum += primes[high++];
		}
	}
	printf("%d", cnt);
}

 

에라토스테네스의 체 + 투 포인터 문제

 

소수들 담아놓는 데 벡터를 써서...

투 포인터의 high가 인덱스를 넘어서니까..

자꾸 인덱스 초과 참조해서 어쩌지 했는데

 

이거 어떻게 더 잘 하는 방법이 있었는데

잘 안되네 머였더라

 

->확인해보니까 걍 배열 쓰고 크기를 하나 더 해줌.. 

쩝