하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.
N이 4000000까지라 N까지의 모든 소수를 vector에 넣을 수 있다.
그러므로 4000000까지의 모든 소수를 구해 vector에 넣어주고, 그 값들을 이용해 구간합 알고리즘을 위한 배열을 하나 만들어준다.
전체 구간내의 특정한 구간(합이 N이되는 구간)을 전부 구해야 하기 때문에 투포인터를 이용해주어야 한다.
left와 right pointer를 둘다 소수vector의 초항으로 잡아주고,
sum[right] - sum[left]가 N보다 크면 left += 1
sum[right] - sum[left]가 N보다 작으면 right += 1
sum[right] - sum[left]가 N이면 정답을 가리키는 변수에 +1해주고, right += 1을 해주면 된다.
나는 이 문제에서 4000000까지의 소수를 구하기 위해
bool isprime(int a){
for(int i=2; i*i<=a; i++){
if(a%i == 0)
return false;
}
return true;
}
sqrt(N)까지를 비교해주는 방식을 썼다.
이것보다는 에라토스테네스의 채 방식을 써주는 것이 좋다.
2~N까지의 모든 정수를 토대로, 그 정수의 배수를 체크해주는 방식이다.
에라토스테네스의 채는 거의 선형시간에 유사한 시간이 걸리므로, 위의 내가 기술한 방식보다 훨씬 시간이 덜걸린다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, sum_arr[1000001], ans;
vector<int>prime;
bool isprime(int a){
for(int i=2; i*i<=a; i++){
if(a%i == 0)
return false;
}
return true;
}
// void dfs(int st, int dest){
// if(dest > prime.size()) return;
// if(prime[dest-1] > N) return;
// if(sum_arr[dest] - sum_arr[st-1] == N){
// ans += 1;
// dfs(st, dest+1);
// return;
// }
// if(sum_arr[dest] - sum_arr[st-1] > N){
// dfs(st+1, dest);
// }else if(sum_arr[dest] - sum_arr[st-1] < N){
// dfs(st, dest+1);
// }
// }
int main(){
cin>>N;
for(int i=2; i<=4000000; i++){
if(isprime(i))
prime.push_back(i);
}
for(int i=1; i<=prime.size(); i++){
sum_arr[i] = sum_arr[i-1] + prime[i-1];
}
// dfs(1,1);
int left=1, right = 1;
while(left <= right && right <= prime.size()){
if(sum_arr[right] - sum_arr[left-1] >N)
left += 1;
else if(sum_arr[right] - sum_arr[left-1] < N)
right += 1;
else{
ans += 1;
right += 1;
}
}
cout<<ans;
}
dfs, while둘다 똑같다.