백준 1644: 소수의 연속합

문제 요약

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)
  
  하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.
  
  자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

문제 분류

• 수학
• 정수론
• 두 포인터
• 소수 판정
• 에라토스테네스의 체

문제 풀이

각 수가 소수인지 bool타입의 배열로 판정 결과를 저장하였다. true이면 소수, 그렇지 않으면 합성수이다.

우선 모든 수가 소수라고 가정하고, 에라토스테네스의 체를 이용하여 소수 판정을 해주었다.

그리고 i와 j를 이용하여 탐색하는데, sum은 i~j의 합이다.

sum이 n보다 작다면, j를 다음 소수로 이동시키고, 해당 j값을 누적시킨다.
sum이 n 보다 크다면, 현재 sum에서 i만큼 빼고, i를 다음 소수로 이동시킨다.
sum이 n과 같다면, cnt++후, j를 다음 소수로 이동시켜서 해당 j를 누적시킨다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#define MAX 4000001

using namespace std;

bool isPrime[MAX];

int main()
{
	int n, i, j, cnt = 0, sum;
	cin >> n;
	memset(isPrime, 1, sizeof(isPrime));
	for (i = 2; i < MAX / 2; i++)
		for (j = 2; i * j < MAX; j++)
			isPrime[i * j] = false;

	sum = 2;
	for (i = 2, j = 2; i <= j; ) {
		if (sum < n) {
			while (!isPrime[++j]);
			sum += j;
		}
		else if (sum > n) {
			sum -= i;
			while (!isPrime[++i]);
		}
		else {
			cnt++;
			while (!isPrime[++j]);
			sum += j;
		}
	}
	cout << cnt;
	return 0;
}