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

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

1644번: 소수의 연속합

 

접근 방법

주어진 값 보다 작거나 같은 소수를 모두 구해 리스트에 담았다.

 

그 후 for문을 이용해서 소수 리스트의 0번째 값부터 차례로 더하는데,

주어진 값 N보다 작거나 같을 때&&소수 리스트를 모두 방문할 때 까지 더한다.

 

만약 더하는 중에 더한 값이 N과 같아지면 count++를 하였다.

 

 

소스 코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static List<Integer> primeNumbers = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();

        setPrimeNumbers(N);

        int count = 0;

	// 소수 리스트를 0번째부터 차례로 더해 값이 일치하는 경우를 확인
        for (int i = 0; i < primeNumbers.size(); i++) {
            int total = 0;
            int index = i;

            while (total <= N && index < primeNumbers.size()) {
                total += primeNumbers.get(index);
                index++;

                if (total == N) {
                    count++;
                    break;
                }
            }
        }

        System.out.println(count);
    }

	// 유클리드의 체 알고리즘을 이용해 소수를 구하는 메서드
    private static void setPrimeNumbers(int max) {
        boolean[] isNotPrime = new boolean[max + 1];

        isNotPrime[0] = true;
        isNotPrime[1] = true;

        for (int i = 2; i < isNotPrime.length; i++) {
            int next = i + i;

            if (!isNotPrime[i]) {
                while (next <= max) {
                    isNotPrime[next] = true;
                    next += i;
                }
            }
        }

        for (int i = 2; i < isNotPrime.length; i++) {
            if (!isNotPrime[i]) {
                primeNumbers.add(i);
            }
        }
    }
}