투포인터. 소수의 연속합

문제

N이 주어졌을때, 연속된 소수의 합으로 N이 될수있는 경우의 수를 구하는 문제이다.

해결방향성

소수 배열을 구간 합을 구하는 방법으로 접근한다. 그러기위해선 N이하의 소수가 저장되어있는 배열이 필요한데, 이 소수를 구하는 과정에서 실행속도가 차이가 난다.
1. 단순히 이중반복문을 돌려 1과 자기자신외 약수가 있는지 판단하는 방법이다.
범위는 N-1까지. 이건 실행시간이 꽤걸린다.
2. 따라서 <= sqrt(N)로 나눠 반쪽만 구하는 방법을 쓸수있는데, 실행시간을 줄일순있지만 답을 구하는데 2000ms(2초)가 걸렸다.
3. 따라서 소수를 구하는데 최적화된 에라토스테네스의 체를 사용하였는데, 실행시간이 200ms(0.2초)대로 가장 빨랐다.
투포인터 방법은 부분합을 구하므로 두 포인터 모두 0부터 시작해서, end == len일때 break 해주면된다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static ArrayList<Integer> primeNumberArray;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        primeNumberArray = new ArrayList<>();
        eratos();
        /*for (int i = 2; i <= N; i++) {
            if (primeNumber(i)) {
                primeNumberArray.add(i);
            }
        }*/

        int len = primeNumberArray.size();
        int[] primeNumberarr = new int[len + 1];

        for (int i = 0; i < len; i++) {
            primeNumberarr[i] = primeNumberArray.get(i);
        }

        int start = 0;
        int end = 0;
        int sum = 0;
        int count = 0;

        while (start <= end) {
            if (sum == N) {
                count++;
            }
            if (sum >= N) {
                sum -= primeNumberarr[start++];
            } else if (end == len) {
                break;
            } else{ // sum < N
                sum += primeNumberarr[end++];
            }
        }

        bw.write(String.valueOf(count));

        bw.flush();
        br.close();
        bw.close();
    }

    private static void eratos() {
        boolean[] prime = new boolean[N + 1];

        // 소수가 아닌것을 true
        prime[0] = prime[1] = true;
        for (int i = 2; i * i <= N; i++) {
            if (!prime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    prime[j] = true;
                }
            }
        }

        for (int i = 0; i <= N; i++) {
            if (!prime[i]) {
                primeNumberArray.add(i);
            }
        }
    }

    /*private static boolean primeNumber(int num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }*/
}

결론

일단 N이 400만까지다 보니, N의 개수가 매우 많아지면 에라토스테네스의 체 성능이 급상승한다.
따라서 알아두면 좋을것같다.
방법은 prime을 i x i <= N 까지의 범위를 뒤지는데, 소수가 아닌것들을 나누는 소수의 제곱수부터 N까지 지워나간다. 갈수록 겹치는 부분이 많아져서 +i만큼 증가시켜도되고, 애초에 2부터 시작해서, 앞수들중 겹치는 수가 왠만하면 없다. 따라서 i x i부터 시작해도 무방하다.
하여튼, 마지막으로 분류된 소수를 arraylist에 넣은다음, 투포인터를 사용해서 연속합을 구하면된다.