(C++) BOJ/백준 1644 - 소수의 연속합

문제 출처 : BOJ 1644 - 소수의 연속합 www.acmicpc.net/problem/1644

 

투 포인터를 배운 기념으로 연습 문제를 풀어보았다.

앞서 풀었던 2003 수들의 합 2 문제와 상당히 유사하다.

 

최종 코드

#include <iostream>
using namespace std;
#define MAX 4000001

int prime[MAX];

int main() {
	int n, l = 2, r = 2, sum = 0, cnt = 0;
	cin >> n;
	for (int i = 2; i < n; i++)
		prime[i] = 0;
	for (int i = 2; i <= n; i++) {
		for (int j = 2; i * j <= n; j++)
			prime[i * j] = 1;
	}

	while (1) {
		if (sum >= n) {
			sum -= l;
			while (prime[++l]) {}
		}
		else if (r > n) break;
		else {
			sum += r;
			while (prime[++r]) {}
		} 

		if (sum == n) cnt++;
	}

	cout << cnt << '\n';

	return 0;
}

 

소수는 0, 아닌 수는 1로 나타나는 배열 prime을 만들어주고,

for문을 사용하여 소수가 아닌 수들은 1로 초기화 시켜주었다.

 

while문 내에서는 투포인터를 이용하여

sum == n이 될 때마다 cnt를 1씩 증가시켜주었다.

 

수들의 합 2 문제와 다른 점은

l과 r을 무작정 늘려주면 소수가 아닌 수들을 더하거나 빼게 되므로,

prime[l]과 prime[r]이 소수인지 아닌지 확인하는 while문을 추가했다.