하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.
자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.
소수판별을 위해 '에라토스테네스의 체 알고리즘' 과 연속적인 소수의 합이라는 점에서 '구간합' 을 이용하면 문제를 해결할 수 있다. 이 때, 누적합의 윈도우값을 계산하기 위해 '투포인터' 를 사용한다.
1을 입력 받는 경우엔 0을 리턴하도록하여, 런타임에러(outOfIndex)가 발생하지 않도록한다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int max = n;
boolean[] arr = new boolean[max + 1];
int count = 0;
if (n < 2) {
System.out.println(0);
return;
}
Arrays.fill(arr, true);
// 소수리스트
ArrayList<Integer> primeList = new ArrayList<>();
// 부분합 리스트
ArrayList<Integer> sumList = new ArrayList<>();
// 소수 구하기 - 에라토스테네스의 체
for (int i = 2; i <= Math.sqrt(max); i++) {
if (arr[i]) {
int j = 2;
while (i * j <= max) {
arr[i * j] = false;
j++;
}
}
}
int sum = 0;
for (int i = 2; i <= max; i++) {
// 소수 담기
if (arr[i]) {
primeList.add(i);
sum += i;
sumList.add(sum);
if (sum == n)
count++;
}
}
int start = 0;
int end = 0;
while (sumList.get(end) < n)
end++;
while (end < sumList.size()) {
if (sumList.get(end) - sumList.get(start) == n)
count++;
if (sumList.get(end) - sumList.get(start) <= n) {
end++;
}
start++;
}
System.out.println(count);
}
}
연속의 합을 구하는 경우 구간합을 사용한다는 점, 해당 범위를 알기위해 투포인터 알고리즘을 사용하는 등의 사항을 기억하고 있어야할 것 같다.