[BOJ 백준] 소수의 연속합(1644) Java, 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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

 

예제 입력 : 

41

예제 출력 : 

3

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

Java 코드 : 

import java.io.*;
import java.util.*;

// 분수 합 1735 
public class Main {
	
	static final int MAX_NUMBER_SIZE = 4_000_000;

	static boolean[] isNotPrimenumber = new boolean[MAX_NUMBER_SIZE];	// true 소수 아님  / false 소수임
	static ArrayList<Integer> pnList = new ArrayList<Integer>();		// 소수리스트
		
	static int N, ans;
	
	public static void main(String[] args) throws IOException {
		
		// 0-1. 에라토스테네스의 체
		for (int i = 2; i * i < MAX_NUMBER_SIZE; i++)
		{
			if (isNotPrimenumber[i] == false) {
				for (int j = i * i; j < MAX_NUMBER_SIZE; j += i)
				{
					isNotPrimenumber[j] = true;
				}
			}	
		}
		
		// 1. 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		

		// 2. 소수리스트 만들기
		pnList.add(2);
		for (int  i = 3; i<=N; i+=2) {
			if (isNotPrimenumber[i] == false) {
				pnList.add(i);
			}
		}
		

		// 3. 누적합을 이용한 투포인터
		int left, right;
		int sum, ans;
		left = right = 0;
		sum = ans = 0;

		while (true) {
			// 1. 값이 작다 right 늘리자
			if (sum < N) {
				// ** 탈출조건
				if (right >= pnList.size()) {
					break;
				}
				// 누적합 더하고 늘리기
				sum += pnList.get(right);
				right++;
			}

			// 2. 값이 크다 left 늘리자
			else if (sum > N) {
				sum -= pnList.get(left);
				left++;
			}

			// 3. 정답 체크하고 앞으로 나아가자
			else {
				ans++;
				if (right >= pnList.size()) {
					break;
				}
				sum += pnList.get(right);
				right++;
			}
		}

		bw.write(String.valueOf(ans));
		
		bw.flush();
		bw.close();
		br.close();
	}

}

 

C++ 코드 : 

// 소수의 연속합 1644
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <vector>

#define MAX (4000000+3)

using namespace std;

bool isNotPrimenumber[MAX];		// true 소수 아님  / false 소수임

vector<int> pnList;				// 소수리스트
int primeSum[1000000];			// 소수누적합

int main() {
	// 0-1. 에라토스테네스의 체
	for (int i = 2; i * i < MAX; i++)
	{
		if (isNotPrimenumber[i] == false) {
			for (int j = i * i; j < MAX; j += i)
			{
				isNotPrimenumber[j] = true;
			}
		}	
	}

	// 1. 입력
	//freopen("input.txt", "r", stdin);

	int n;
	scanf("%d", &n);

	// 2. 소수리스트 만들기
	pnList.push_back(2);
	for (int i = 3; i <= n; i += 2) {
		if (isNotPrimenumber[i] == false) {
			pnList.push_back(i);
		}
	}

	// 3. 누적합을 이용한 투포인터

	int left, right;
	int sum, ans;
	left = right = 0;
	sum = ans = 0;

	while (1) {
		// 1. 값이 작다 right 늘리자
		if (sum < n) {
			// ** 탈출조건
			if (right >= pnList.size()) {
				break;
			}
			// 누적합 더하고 늘리기
			sum += pnList[right];
			right++;
		}

		// 2. 값이 크다 left 늘리자
		else if (sum > n) {
			sum -= pnList[left];
			left++;
		}

		// 3. 정답 체크하고 앞으로 나아가자
		else {
			ans++;
			if (right >= pnList.size()) {
				break;
			}
			sum += pnList[right];
			right++;
		}
	}

	printf("%d", ans);

	return 0;
}
#endif