[백준] 1644번 : 소수의 연속합

1644번: 소수의 연속합

---

[소수 판정]

1부터 n까지 반복문을 돌며 소수인 것을 prime 배열에 저장했다. 그러면 prime에는 n이하의 소수만 저장되게 된다.

 

이제 이중 루프를 이용해서 prime을 돌며 연속 합이 n보다 같은 경우를 찾아 count를 증가시킨다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static boolean isPrime(int x){
        if(x == 1) return false;

        for(int i=2; i<=Math.sqrt(x); i++)
            if(x % i == 0)
                return false;

        return true;
    }

    static int[] prime = new int[3000000];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()), idx = 0, cnt = 0;

        for(int i=1; i<=n; i++)
            if(isPrime(i))
                prime[idx++] = i;

        for(int i=0; i<idx; i++){
            int sum = 0;

            for(int j=i; j<idx; j++){
                sum += prime[j];

                if(sum >= n){
                    if(sum == n) cnt++;
                    break;
                }
            }
        }
        System.out.println(cnt);
    }
}