C++ / 백준 / 1644 / 소수의 연속합

문제

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

1644번: 소수의 연속합

문제풀이

에라토스테네스의 체를 이용하여 N까지의 소수를 미리 구해둔다.

그 다음 두포인터 부분을 구현하면 된다.

이중 for문, while문으로 구현해봤는데 시간차이가 안났다..

1806번 문제 코드와 거의 비슷하게 구현했는데 이중for문 -> while문으로 바꿨는데 시간초과 나던코드가 통과한것으로 봐선 시간복잡도가 더 적은게 확실한데 왜 여기서는 차이가 없는지 모르겠다.

 

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N(0);
	cin >> N;

	vector<bool>prime(N + 1, true);
	int idx(0);
	int idx2(0);
	for (idx = 2; idx * idx <= N; ++idx)
		for (idx2 = idx; idx * idx2 <= N; ++idx2)
			prime[idx * idx2] = false;
		
	vector<int>seq;
	for (idx = 2; idx <= N; ++idx)
		if (prime[idx]) seq.push_back(idx);
	seq.push_back(0);

	int answer(0);

	idx = 0;
	idx2 = 0;
	int sum(0);
	while (idx2<seq.size()) {		
		if (sum >= N) {
			if(sum==N)
			++answer;
			sum -= seq[idx];
			++idx;
		}
		else {
			sum += seq[idx2];
			++idx2;
		}
	}
	cout << answer;
}