소수의 연속합 (feat. 백준, 1644번)

소수의 연속합
https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
bool tmp[4000000];
vector<int> arr;
void get_arr1(register int N) {
	for (register int i = 2, j; i <= N; i++)
	{
		register int cnt = 0;
		for (j = 2; j <= i; j++)
			if (i % j == 0)
				cnt++;
		if (cnt == 1)
			arr.push_back(i);
	}
}
void get_arr2(register int N) {
	memset(tmp, false, N);
	tmp[0] = tmp[1] = true;
	register int e = sqrt(N);
	for (register int i = 2, j; i <= e; ++i)
		if (!tmp[i])
			for (j = i << 1; j <= N; j += i)
				tmp[j] = true;
	for (register int i = 2; i <= N; ++i)
		if (!tmp[i])
			arr.push_back(i);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	cin >> N;
	get_arr2(N);
	register int s = 0, e = 0, cnt = 0, sum = 0;
	while (s <= e)
		if (sum < N) {
			if (e >= arr.size())
				break;
			sum += arr[e++];
		}
		else if (sum > N) {
			sum -= arr[s++];
		}
		else {
			++cnt;
			if (e >= arr.size())
				break;
			sum += arr[e++];
		}
	cout << cnt;
	return 0;
}
// *&)*@*

소수를 구하는 방식 중 가장 빠른 방법은 "에라토스테네스의 체" 를 이용하는 방법입니다.

소수 구하기 (feat. 백준, 1929번)

재귀나 for문을 이용한 체크는 시간 초과 판정을 받게 되는 것을 확인하였습니다.