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

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

1644번: 소수의 연속합

 

소수는 에라토스테네스의 체 알고리즘을 이용해서

소수만 따로 arraylist에 모아 두고,

구해놓은 arraylist를 이용해서 투포인터 알고리즘을 쓰면 연속합의 개수를 쉽게 구할 수 있다.

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

public class P1644 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		boolean[] prime = new boolean[n + 1];
		ArrayList<Integer> arr = new ArrayList<>();
		for (int i = 2; i < n + 1; i++) {
			if (prime[i] == false) {
				arr.add(i);
				for (int j = i * 2; j < n + 1; j = j + i) {
					prime[j] = true;
				}
			}
		}

		int start = -1, end = -1, sum = 0, count = 0;

		while (end < arr.size() && start <= end) {
			if (sum <= n) {
				if (end == arr.size() - 1)
					break;
				sum += arr.get(++end);
			} else {
				sum -= arr.get(++start);
			}

			if (sum == n) {
				count++;
			}

		}

		System.out.println(count);
	}

}