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

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

1644번: 소수의 연속합

 

1) n까지의 소수를 구한다. -> 에라토스테네스의 체를 사용하여 구해야 시간초과가 나지 않는다!

2) 소수 연속 합을 확인한다.

 

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

public class Main {
	static int n;

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

		// 에라토스테네스의 체
		boolean[] arr = new boolean[n + 1];
		arr[0] = arr[1] = true;
		for (int j = 2; j * j <= n; j++) {
			if (!arr[j]) {
				for (int i = j*j; i <= n; i+=j) {
					arr[i]=true;
				}
			}
		}

		int result = 0;
		int sum = 0;
		for (int i = 2; i <= n; i++) {
			if (arr[i]) {
				continue;
			}
			for (int j = i; j <= n; j++) {
				if (!arr[j]) {
					sum += j;
					if (sum > n) {
						sum = 0;
						break;
					} else if (sum == n) {
						result++;
						sum = 0;
						break;
					}
				}
			}
		}

		System.out.println(result);
	}

}