[백준 - 1644] 소수의 연속합 - Java

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

1644번: 소수의 연속합

 

에라토스테네스의 체를 사용해서 푼 간단한 문제이다.

에라토스테네스의 체를 사용해서 2부터 입력된 숫자까지의 소수를 구하여 새로운 Array에 저장하고,

찾은 소수와 합해서 입력된 숫자가 되는 다른 소수가 있는지 찾는다.

 

 

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> primes = new ArrayList<>();

        boolean[] isNotPrime = new boolean[N+1];
        isNotPrime[0] = isNotPrime[1] = true;
        for(int i=2; i<=N; i++){
            if(!isNotPrime[i]){
                primes.add(i);
                for(int j=i*2; j<=N; j+=i){
                    isNotPrime[j] = true;
                }
            }
        }
        int count = 0;
        int p1 = 0, p2 = 0;
        while(p1<primes.size()){
            int sum = 0;
            while(p2<primes.size()){
                sum += primes.get(p2);
                if(sum > N) {
                    p1++;
                    p2 = p1;
                    break;
                }
                else if(sum ==  N){
                    count ++ ;
                    p1 ++;
                    p2 = p1;
                    break;
                }
                else {
                    p2++;
                }
            }
            if((p1+1)==primes.size()&&p2==primes.size()) {
                break;
            }
        }

        System.out.println(count);

    }
}