백준

[백준] 1644 소수의 연속합

거북이같은곰 2021. 11. 16. 07:17


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

public class Main {
	static boolean[] prime;
	static ArrayList<Integer> list;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		prime = new boolean[N+1];
		isPrimeNumber(N);
		System.out.println(result(N));
	}
	static void isPrimeNumber(int N) {
		list = new ArrayList<>();
		for(int i = 2; i <= N; i++) {
			if(!prime[i])
				list.add(i);
			for(int j = i+i; j<=N; j += i) {
				if(prime[j] == true)
					continue;
				else {
					prime[j] = true;
				}
			}
		}
	}
	static int result(int N) {
		int ans = 0;
		int cnt = 0;
		for(int i = 0; i < list.size(); i++) {
			for(int j = i; j < list.size(); j++) {
				ans += list.get(j);
				if(ans == N) {
					cnt++;
					ans = 0;
					break;
				}
				else if(ans > N) {
					ans = 0;
					break;
				}
			}
		}
		return cnt;
	}
}

에라토스테네스의 체 수정 필요

i + i -> i * i