백준 1644 소수의 연속합 Java [에라토스테네스의 체]

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

1644번: 소수의 연속합

 

소수를 구하는 방법은 2가지 있다

1. 숫자를 증가시켜가면서 소수로 나눠지는지 확인하기

2. 에라토스테네스의 체 사용하기

 

숫자가 충분히 크니까 에라토스테네스의 체를 사용하는게 시간복잡도 측면에서 이득

 

에라토스테네스의 체는

2부터 시작해서 2를 제외한 2의 배수를 다 소수가 아니라고 체크하고

3을 제외한 3의 배수를 다 소수가 아니라고 체크한다

숫자를 증가시켜가면서 체크안된 숫자(소수)의 배수를 소수가 아니라고 체크하는 과정을 반복한다

그리고 연속된 수의 합이 N이면 count 해준다

이 방법은 숫자를 하나씩 증가시켜가면서 소수를 계속 더해주고

값이 N보다 크면 가장 처음에 추가한 값부터 N보다 작아질 때까지 빼준다

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        boolean[] prime = new boolean[N+1];
        for (int i = 2; i <= N; i++) {
            if (prime[i]) continue;
            for (int j = i + i; j <=N; j += i) {
                prime[j] = true;
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        int j = 2, result = 0, sum = 0;
        while (!queue.isEmpty() || j <= N) {
            if (sum < N && j <= N) {
                if (!prime[j]) {
                    sum += j;
                    queue.add(j);
                }
                j++;
            }
            else if (sum == N) {
                result++;
                sum -= queue.poll();

            } else {
                sum -= queue.poll();
            }
        }
        System.out.println(result);
    }
}

큐를 만들어서 가장 처음에 넣은 값을 빼줬는데 큐에 넣고 빼는 과정 때문에 시간이 좀 더 걸린 것 같다

에라토스테네스의 체도 짝수값들 먼저 초기화해주고

i는 3부터해서 i+=2로 증가시키고 (홀수값들만)

j+= i*2(변수에 담아서) 계산(홀수값들만, 홀수+짝수=홀수)하면 좀 더 시간을 단축할 수 있을 것 같다