b1644 소수의 연속합

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

 

 

 

주어진 자연수 N을 소수의 연속된 합으로 나타내는 경우의 수를 구하는 문제다.

 

먼저, getArr 메서드를 통해 2부터 N까지의 소수들을 구한다.

이 과정에서 에라토스테네스의 체를 사용하여 소수를 빠르게 판별한다.

 

isPrime 배열을 초기화하고, 2부터 시작해 소수의 배수를 모두 제거해가며

소수 여부를 판별하여, primes 리스트에 소수들만 저장한다.

이후 리스트를 배열로 변환해 반환하여 효율적으로 소수 리스트를 사용할 수 있게 한다.

main 메서드에서는 먼저 N의 값을 입력받고,

getArr를 통해 구한 소수 배열 arr을 활용해 문제를 풀어간다.

 

start와 end 포인터를 통해 배열 내 소수의 연속합을 확인하며,

합이 N과 같을 경우 경우의 수 answer를 1 증가시킨다.

 

만약 합이 N보다 크다면, 해당 구간을 종료하고 다음 시작 인덱스로 넘어간다.

각 start 인덱스에 대해 새로운 연속합을 구하고,

조건에 맞는 구간을 찾는 식으로 반복한다.

 

최종적으로 구해진 경우의 수 answer를 출력하여 N을 소수의 연속된 합으로 나타내는

모든 경우의 수를 계산한다.

 

 

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

public class b1644 {

    private static int[] getArr(int N){
        boolean[] isPrime = new boolean[N + 1];
        List<Integer> primes = new ArrayList<>();

        for (int i = 2; i <= N; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }

        return primes.stream().mapToInt(Integer::intValue).toArray();
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = getArr(N);
        int size = arr.length, sum = 0, answer = 0;

        for(int start = 0 ; start < size ; start++){
            sum = arr[start];
            if(sum == N){
                answer++;
                continue;
            }
            for(int end = start + 1 ; end < size ; end++){
                sum+=arr[end];
                if(sum > N) break;
                if(sum == N){
                    answer ++;
                    break;
                }

            }
        }
        System.out.println(answer);
    }
}