[백준문제풀이] 1644 소수의 연속합

풀이일시 : 2020-12-24

​

 

문제 :

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

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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

​

​

풀이 :

에라토스테네스의 체로 소수를 전부 판별해 놓는다.

dbstndi6316.tistory.com/53

[기본문제풀이] 에라토스테네스의 체

이후 투포인터 알고리즘으로 풀이할 수 있다.

dbstndi6316.tistory.com/39

[개념정리] Two pointer algorithm

#include <iostream>

using namespace std;
const int MAX = 4000000;

int a[MAX];
int res[MAX];
int N;

void eratosthenes() { //소수를 판별해서 배열을 만들자
	for (int i = 2; i <= MAX; i++) {
		a[i] = i; //배열을 다 초기화해준다.
	}
	for (int i = 2; i <= MAX; i++) {
		if (a[i] == 0) continue; //이미 방문했던곳은 방문하지않는다.
		for (int j = i + i; j <= MAX; j += i) { //배수
			a[j] = 0; //방문처리
		}
	}
	int cnt = 0;
	for (int i = 2; i <= MAX; i++) {
		if (a[i] != 0) //0으로 변하지 않은 남은 소수부분 출력
			res[cnt++] = i; //투포인터 알고리즘에 사용하기 위해 이와같은 형식으로 res 생성
	}
}

int main() {
	eratosthenes();
	cin >> N;
	int M;
	for (int i = 0; i < MAX; i++) {
		if (res[i] >= N) {
			M = i + 1;//쓰는 인자 개수 (투포인터 알고리즘 사용 위해 M설정)
			break;
		}
	}
	//투포인터 알고리즘 이용하자
	int sum = 0, count = 0, left = 0, right = 0;
	while (1) {
		if (sum >= N) {
			sum -= res[left++];
		}
		else if (right == M)
			break;
		else
			sum += res[right++];
		if (sum == N)
			count++;
	}
	cout << count << endl;
	return 0;
}