[JAVA] 백준 1644 소수의 연속합

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

1644번: 소수의 연속합

 

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

 

ex) 3 : 3(1개)

      41 : 2+3+5+7+11+13 = 11+13+17 = 41 (3개)

      53 : 5+7+11+13+17 = 53 (2개)

 

- 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에 3+5+5+7과 같은 표현도 적합하지 않다. 

 

- 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램 

 

 

문제 풀이 

 

소수 구하기 

[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java) (tistory.com)

[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java)

[백준] 1644번 소수의 연속합 (자바 풀이) (tistory.com)

[백준] 1644번 소수의 연속합 (자바 풀이)

 

- 에라토스테네스의 체와 투 포인터를 이용해 풀이 

- 만약 sum이 N과 같다면 count를 1증가시키고, N보다 작다면 end 포인터를 오른쪽으로 한 칸 옮기고 sum에 더해줌

- N보다 크다면 start 포인터가 가리키는 값을 감소시키고 start 포인터를 오른쪽으로 한칸 옮김 

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        
        boolean isPrime[] = new boolean[N+1];
        ArrayList<Integer>Primes = new ArrayList<>();
        
        //에라토스테네스의 체 
        isPrime[0]= isPrime[1] = true;
        for(int i=2; i*i<=N; i++)
        {
        	if(!isPrime[i])
        	{
        		for(int j=i*i; j<=N; j+=i)
        		{
        			isPrime[j] = true;
        		}
        	}
        }
        
        for(int i=1; i<=N; i++)
        {
        	if(!isPrime[i])
        	{
        		Primes.add(i);
        	}
        }
        
        int start = 0;
        int end = 0;
        int sum = 2;
        int count = 0;
        int size = Primes.size();
        
        while(start<size && end <size)
        {
        	if(sum==N)
        	{
        		count++;
        		sum -= Primes.get(start);
        		start++;
        	}
        	else if(sum >N)
        	{
        		sum-=Primes.get(start);
        		start++;
        	}
        	else
        	{
        		end++;
        		if(end>=size) break;
        		sum+=Primes.get(end);
        	}
        }
        
       
        
        bw.write(String.valueOf(count));
        
        bw.flush();
        bw.close();
        
    }
}