하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.
예제
풀이
에라토스테네스의 체와 브루트포스를 활용하여 문제를 해결하였습니다.
이 문제를 풀기 위해선 범위 내에 소수를 구할 필요가 있었고 그것을 에라토스테네스의 체를 사용하여 함수로 작성하였습니다.
소수 배열을 구했으면 전체 경우의 수를 탐색하면서 목표값과 일치하는지 확인하였습니다.
단, 더한 값이 목표값보다 커지면 해당 반복문은 종료하였습니다.
ps) 이 문제를 위의 방법으로 해결하고 혹시 연속합을 구하는 알고리즘을 적용하면 더 빨리 풀리지 않을까 시도해 보았습니다.
연속합은 배열에 해당 인덱스 이하의 값을 더 해 놓고 SUM[범위의 끝] - SUM[범위 시작 - 1]로 범위의 연속합을 구하는 알고리즘입니다.
단순히 범위의 연속합을 구하는 것이라면 더 빠르게 풀리겠지만 이 문제는 전체 탐색하면서 진행하다보니 연속합 알고리즘을 적용해도 매번 더하는 방식과 계산 횟수는 동일하고 오히려 연속합 배열을 만드는 시간 만큼 시간이 더 걸렸습니다.
백준 제출 결과 기준으론 4ms가 더 걸렸습니다.
성공 코드
#include <iostream>
#include <vector>
using namespace std;
//custum function
vector<int> getPrimeNum(int limit)
{
vector<int> primeNumArr;
vector<bool> primeNumCheck(limit + 1);
//에라토스테네스의 체
for (int num(2); num <= limit; ++num)
{
//방문하지 않은 수이면 소수이다
if (!primeNumCheck[num])
{
//배열에 추가하고
primeNumArr.push_back(num);
//배수들을 방문처리 해준다
int checkNum(num);
while (checkNum <= limit)
{
primeNumCheck[checkNum] = true;
checkNum += num;
}
}
}
return primeNumArr;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
////////////////////////////////////
//에라토스테네스의 체를 활용하여 입력된 값 이하의 소수 배열을 생성한다
//생성된 소수 배열을 연속적으로 더해 가면서 목표 값이랑 동일한지 확인 한다
//단 더한 값이 목표값보다 커지면 해당 반복을 중지한다
//Declaration
int target = 0;
int answer = 0;
cin >> target;
//Solution
vector<int> primeNumArr = getPrimeNum(target);
//큰 값부터 확인한다.
for (int index = primeNumArr.size() - 1; index >= 0; --index)
{
int sumVal = primeNumArr[index];
int sumIndex = index;
//연속해서 더한 값이 목표 값과 일치하는지 확인하면서 진행하고
//더한 값이 목표값보다 커지면 종료한다
while (sumVal <= target)
{
if (sumVal == target)
{
++answer;
break;
}
if (sumIndex > 0)
{
sumVal += primeNumArr[--sumIndex];
}
else
{
break;
}
}
}
//Output
cout << answer << '\n';
return 0;
}
