[백준] 1644번: 소수의 연속합 C++로 풀어보기

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

1644번: 소수의 연속합

1644번 설명

 

생각

일단 숫자를 입력받으면 숫자보다 작은 수들 중에 소수인 것들을 모아서 배열에 집어넣어야 한다.

그리고 투 포인터를 활용하여 그 배열 안에서 n과 같은 연속합이 있는지 찾아보면 된다.

 

소수를 찾는 방법은 에라토스테네스의 체를 활용하면 된다.

https://danidani-de.tistory.com/50

에라토스테네스의 체(소수 찾기) C++ / 과정 / 시간복잡도 :: DANIDANI

위의 링크에서 에라토스테네스의 체에 대한 설명과 C++ 코드가 있으니 참고하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int arr[1000005]; // 배열의 크기를 작게 잡으면 컴파일 에러가 뜬다
int anscnt = 0; // 자연수 n을 연속된 소수의 합으로 나타낼 수 있는 경우의 수

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin >> n;

	// 에라토스테네스의 체를 이용해서 소수를 판별
	vector<bool> v(n + 1);
	v[1] = true; // 1을 소수가 아니므로

	for (int i = 2; i <= sqrt(n); i++) {
		if (v[i]) {
			continue;
		}

		for (int j = i + i; j <= n; j += i) { // 배수 제거
			v[j] = true;
		}
	}

	int cnt = 0; // cnt = 소수의 개수
	for (int i = 2; i <= n; i++) {
		if (!v[i]) {
			arr[cnt] = i;
			cnt++;
		}
	}

	int en = 0;
	int total = arr[0]; // 수의 합을 저장하는 변수

	for (int st = 0; st < n; st++) {
		while (en < cnt && total < n) { // en이 소수의 개수보다 작고 total이 n보다 작다면
			en++; // en을 한 칸 오른쪽 옆으로 옮긴다
			if (total == n) { // total = n이면
				anscnt++; // anscnt에 1을 더해준다
			}
			if (en != cnt) {
				total += arr[en]; // arr[en]을 total에 더해준다
			}
		}
		if (en == cnt) { // 범위에 벗어났다면
			break;
		}

		if (total == n) { // total = n이면
			anscnt++; // anscnt에 1을 더해준다
		}

		total -= arr[st]; // total에서 arr[st]를 빼준다
	}
	cout << anscnt; // 정답 출력
 }

 

처음에 배열의 크기를 100005로 줬다가 컴파일 에러가 나왔다. 배열의 크기를 더 크게 해줬더니 해결되었다.

 

결과

1644번 결과