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

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

문제

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

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

---

풀이

Algorithm

이 문제는 두 포인터 algorithm을 통해 간단하게 구현할 수 있다.

 

1. N보다 작은 소수들을 저장하는 리스트를 만들고
2. 그 리스트에서 두 포인터 방식을 이용하여 합이 N과 같아질 때를 찾는다.

1. N보다 작은 소수들을 저장하는 리스트(prime) 만들기

1부터 N까지의 숫자들 중 for문을 돌려 소수인지 판별하고, 소수가 맞다면 prime 리스트에 넣어준다.

이때 짝수는 어차피 2 빼고 모두 소수가 아니기 때문에, prime list에 먼저 2를 넣어주고 홀수에 대해서만 소수인지 검사하기로 한다.

int prime[4000000] = { 2, };
int n = 1; // N보다 작은 소수의 개수 = prime의 원소 개수

• 소수인지 판별하는 함수

bool isPrime(int i) {
	for (int j = 3; j <= sqrt(i); j += 2) {
		if (i % j == 0) return false;
	}
	return true;
}

i에는 홀수들만 넣을 것이기 때문에 자신의 제곱근보다 작은 홀수들로만 나누어보고 이때 0이 되는 것이 있다면 소수가 아니고, 모두 통과한다면 소수이다.

• 3~N까지의 홀수 for문 돌리기

	for (i = 3; i <= N; i += 2) {
		if (isPrime(i)) {
			prime[n] = i;
			n++;
		}
	}

자신보다 작은 홀수들만 검사하여 홀수라면 prime 리스트에 저장한다.

 

2. prime(1~N까지의 소수를 저장한 list)에서 두 포인터 방식을 이용하여 합이 N과 같아질 때를 찾는다.

변수 설명

int p1 : 연속된 소수의 첫번째 숫자를 가리키는 변수 / 초기값 0

int p2 : 연속된 소수의 마지막 숫자를 가리키는 변수 / 초기값 0

int sum : 연속된 소수의 합을 저장하는 변수 / 초기값 2

 

우선 연속된 소수가 한 개 이상이어도 되므로 초기에 0번째 숫자, 즉 2를 가리키고 시작한다.

연속된 소수 배열은 p1이 가리키는 곳부터 ~ p2가 가리키는 곳까지 라고 보면 된다.

	while (true) {
		if (p1 > p2 || p2 >= n) // 종료 조건
			break;
		if (sum < N) { // 1. 합이 N보다 더 작으면
			p2++; // 연속된 소수를 하나 추가
			sum += prime[p2]; // sum에도 그 숫자를 더해주기
		}
		else if (sum > N) { // 2. 합이 N보다 크면
			sum -= prime[p1]; // 연속된 소수 하나를 빼주기
			p1++; // 연속된 소수의 첫번째 index를 하나 증가
		}
		else { // 3. 합이 N과 같다면
        	ncount++; // 연속된 소수 배열을 찾았으므로 개수 count 1 증가
            // 또 찾을 수도 있으므로!
			sum -= prime[p1]; // 첫번째 숫자를 빼주고
			p1++;
			p2++; // 또 다음 숫자를 추가해주어 새로운 소수 배열을 만들어 검사하기
			sum += prime[p2];
		}
	}

 

Code

#include <iostream>
#include <math.h>
using namespace std;
int N;
int prime[4000000] = { 2, }; // N보다 작은 소수들을 저장하는 리스트
int n = 1; // N보다 작은 소수들의 개수
int ncount = 0; // 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수

bool isPrime(int i) {
	// 자신의 제곱근보다 작은 홀수들로 나누어 본다.
	for (int j = 3; j <= sqrt(i); j += 2) {
		if (i % j == 0) return false;
	}
	return true;
}

int main() {
	int i;
	cin >> N;
    // N 이하의 소수들을 모두 prime 배열에 저장
	for (i = 3; i <= N; i += 2) {
		if (isPrime(i)) {
			prime[n] = i;
			n++;
		}
	}
    
    // 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 과정
	int p1 = 0, p2 = 0, sum = 2; // 초기값
	while (true) {
		if (p1 > p2 || p2 >= n) // 빠져나올 조건
			break;
		if (sum < N) {
			p2++;
			sum += prime[p2];
		}
		else if (sum > N) {
			sum -= prime[p1];
			p1++;
		}
		else { // sum이 N과 같아지면
			sum -= prime[p1];
			p1++;
			p2++;
			sum += prime[p2];
			ncount++;
		}
	}
	
	cout << ncount << '\n';
	return 0;
}