소수의 연속합

알고리즘 구분 : 에라토스테네스의 체, 수학, 정수론, 소수 판정, 두 포인터

문제

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

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과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력
첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

(1)
예제 입력 1
20

예제 출력 1
0

(2)
예제 입력 2
3

예제 출력 2
1

(3)
예제 입력 3
41

예제 출력 3
3

(4)
예제 입력 4
53

예제 출력 4
2

문제 풀이

결국 사용 가능한 모든 소수를 찾아야 하기에 에라토스테네스의 체를 활용하여 주어진 범위 안에서 사용가능한 소수를 찾아 특정 벡터에 저장하였다.
이후 해당 벡터에 있는 소수들의 범위를 조절하면서 가능한 모든 경우의 수를 찾는 방식으로 풀면 된다.
나는 처음에 소수를 구한 이후 가능한 모든 경우의 수를 카운팅하는 방식으로 이중반복문을 구현하였는데, 해당 풀이로도 AC를 받았다.
결론적으로, 두 포인터 방식은 활용하지 않아도 되길래 의문을 가지고 있었는데, 질문 게시판에서 가능한 이유를 알게 되었다.

혹시, 나처럼 이중 반복문으로 구현하는 것에 대한 이유를 확인하고 싶다면 이 게시글을 확인하면 될 것 같다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int num;
bool primeNum[4000001];
vector<int> prime;
int cnt[4000001];
int solprimee(int num);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 에라토스테네스의 체 Default
    memset(primeNum, 1, sizeof(primeNum));
    primeNum[0] == false;
    primeNum[1] == false;
    for(int i = 2; i < sqrt(4000000) + 1; i++) {
        if(primeNum[i]) {
            for(int j = i + i; j < 4000001; j += i) {
                primeNum[j] = false;
            }
        }
    }

    for(int i = 2; i < 4000001; i++) {
        if(primeNum[i]) {
            prime.push_back(i);
        }
    }

    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < prime.size(); i++) {
        int sum = 0;
        for(int j = i; j < prime.size(); j++) {  
            sum = sum + prime[j];

            if(sum > 4000000) {
                break;
            }
            else {
                cnt[sum]++;
            }
        }
    }

    cin >> num;

    cout << cnt[num] << endl;

    return 0;
}


/*
최대 소수의 범위가 400,000이므로 시작 당시
에라토스테네스의 체로 모든 소수들 구해놓고
각 수를 만들 수 있는 경우의 수를 찾기
*/

• 문제 출처 : https://www.acmicpc.net/problem/1644
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.