[백준] 1644번: 소수의 연속합

문제 링크: [백준] 1644번: 소수의 연속합

오늘도 꾸준히 알고리즘을 공부해봅시다! 

매일 꾸준히 조금씩 풀다 보면 저도 언젠가 잘해지지 않을까요?

며칠 안 남은 20년, 더욱 힘내봅시다!

문제

---

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

• 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이 주어지면 연속된 소수의 합이 N이 되는 경우의 수를 구하는 문제였습니다. 

이때 주의할 점으로 연속된 소수의 합을 구할 때, 각각의 소수는 단 한 번씩만 더해져야 한다는 것입니다.

그러려면 먼저 N 이하의 소수를 먼저 구해야 겠죠? N의 최대 크기가 400만이기 때문에 효율적이라고 널리 알려진 에라토네스의 체 방법을 이용하여 소수 배열을 구해보았습니다.

N이하의 소수배열을 구하고 연속된 소수의 부분합을 구하기 위해 투 포인터 기법을 사용하여 부분합이 N이 되는 구간의 수를 구할 수 있었습니다.

#include<bits/stdc++.h>

using namespace std;
int N,l,r,ans;
vector primes,nums;

   	// 에라토네스의 체

void getPrimes(int N){

	nums.resize(N+1,1);		//nums 배열 1로 초기화

	for(int i=2;i<=sqrt(N);i++){

		if(!nums[i]) continue; 	//어떤 수의 배수인 수로 체크되었으므로 continue;
		
		for(int j=2*i;j<=N;j+=i){
			nums[j]=0;
		}
	}

	for(int i=2;i<=N;i++)if(nums[i]) primes.push_back(i);
	
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin>>N;

	getPrimes(N);

	int vecSize=(int)primes.size(); //소수 배열의 크기
	int partialSum=0;		// 부분 합 변수

	// 투 포인터 
	while(1){
		if(partialSum>=N) partialSum-=primes[l++];   // 부분합 감소
		else if(r==vecSize) break;		     
		else partialSum+=primes[r++];  		     // 부분합 증가	
		if(partialSum==N) ans++; 	             
	}
	cout<<ans<<"\n"; return 0; }

부족한 부분이나 궁금한 부분 댓글 감사하겠습니다!.