소수의 연속합 - 1644번

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

 

package BaekJoon.TwoPointer;

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

public class 소수의연속합 {
	
	static boolean[] check =new boolean[4000001];
	static int[]list;
	static ArrayList<Integer>arr = new ArrayList<>();
	static int n;

	public static boolean issosu(int num) {
		
		int n = (int)Math.sqrt(num);
	
		for(int i=2; i<=n; i++) {
			
			if(num%i==0)return false;
			
		}
		
		return true;
		
	}
	
	public static void findsosu() {
		
		check[1]=true;
		int cnt=1;
		for(int i=2; i<=Math.sqrt(4000000); i++) {
			
	
			if(issosu(i)) {
			
			for(int j=i*2; j<=4000000; j+=i) {
					if(check[j]==false) {
					check[j]=true;
					cnt++;
					}
			}
			
			}
			
		}
		
		list = new int[4000000-cnt];
		int idx =0;
		for(int i=1; i<=4000000; i++) {
			
			if(check[i]==false) {
				list[idx]=i;
				idx++;
			}
			
		}
		
	}
	
	
	
	public static void main(String[] args) throws NumberFormatException, IOException {
	
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		findsosu();
		
		for(int i=0; i<list.length; i++) {
		//	System.out.println(list[i]+" ");
		}
		
		int cnt =0;
		
		for(int i=0;i<list.length; i++) {
			
			int j =i;
			int sum = 0;
			while(j<list.length) {
				
				
				sum+=list[j];
				
				if(sum<n) {
					
					j++;
					
				}
				else if(sum==n){
					cnt++;
			//		System.out.println(list[i]+","+list[j]);
					break;
				}
				else {
					break;
				}
				
			}
		}
		
		System.out.println(cnt);
		
		
	}
	

}

- 에라토스테네스체를이용해서 소수인 경우를 모두 찾는다.

- 소수로이루어진 오름차순 배열에서 left pointer와 right pointer로 연속적인 합을 구할 수 있다.