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

예제 입력 1

20

예제 출력 1 

0

예제 입력 2 

3

예제 출력 2 

1

예제 입력 3 

41

예제 출력 3 

3

예제 입력 4 

53

예제 출력 4 

2

---

문제 풀이

 해당 문제는 범위 내 존재하는 소수 구하기(에라토스테네스의 체)와 투 포인터 알고리즘이 합쳐진 문제이다.

 

 주어진 숫자를 연속된 소수의 합으로 나타낼 수 있는 방법을 구하기 위해 우선 에라토스테네스의 체를 통해 해당 숫자 이하의 모든 소수를 먼저 구한다.

public static int[] getPrime(int num) {
		boolean[] visited = new boolean[num+1];
		visited[0] = true;
		visited[1] = true;
		
		for(int i = 2; Math.pow(i, 2) <= num; i++) {
			int c = 2;
			while(c * i <= num) {
				visited[c * i] = true;
				c++;
			}
		}

		ArrayList<Integer> nums = new ArrayList<>();
		
		for(int i = 0; i < visited.length;i++) {
			if(!visited[i]) {
				nums.add(i);
			}
		}
		int[] primes = new int[nums.size()];
		for(int i = 0; i < nums.size();i++)
			primes[i] = nums.get(i);
		return primes;
	}

 

 이후 첫 소수에서 두 포인트로 시작해서 두 포인트 사이의 소수의 합을 숫자와 비교하여 숫자보다 클 경우 왼쪽 포인트를 오른쪽으로, 작을 경우는 오른쪽 포인트를 오른쪽으로 보내면서 소수의 합이 숫자와 같을 경우 answer에 추가해준다.

int left = 0;
int right = 0;

while(right < primes.length) {
    int sum = 0;
    for(int i = left; i <=right; i++) {
        sum+=primes[i];
    }
    if(sum > num) {
        left++;
    }else if(sum < num) {
        right++;
    }else {
        left++;
        answer++;
    }

---

풀이 코드

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


public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static StringTokenizer st;
	public static StringBuilder sb = new StringBuilder();
	public static int INF = 100_000_000;
	public static int[] dx = {0,1,0,-1};
	public static int[] dy = {-1,0,1,0};

	public static void main(String[] args) throws IOException{
		int num = Integer.parseInt(br.readLine());
		int[] primes = getPrime(num);
		
		int answer = 0;
		
		int left = 0;
		int right = 0;
		
		while(right < primes.length) {
			int sum = 0;
			for(int i = left; i <=right; i++) {
				sum+=primes[i];
			}
			if(sum > num) {
				left++;
			}else if(sum < num) {
				right++;
			}else {
				left++;
				answer++;
			}
		}
		System.out.println(answer);

	}
	public static int[] getPrime(int num) {
		boolean[] visited = new boolean[num+1];
		visited[0] = true;
		visited[1] = true;
		
		for(int i = 2; Math.pow(i, 2) <= num; i++) {
			int c = 2;
			while(c * i <= num) {
				visited[c * i] = true;
				c++;
			}
		}

		ArrayList<Integer> nums = new ArrayList<>();
		
		for(int i = 0; i < visited.length;i++) {
			if(!visited[i]) {
				nums.add(i);
			}
		}
		int[] primes = new int[nums.size()];
		for(int i = 0; i < nums.size();i++)
			primes[i] = nums.get(i);
		return primes;
	}
}