[백준 1644] 소수의 연속합 [C]

백준 - 1644

---

풀이

연속된 소수의 합이므로, 소수로만 이루어진 배열에서 투 포인트를 적용하면 된다.

에라토스테네스의 체로 소수가 아닌 것들을 구분하여 소수로만 이루어진 배열을 만들고, 투 포인트 방식으로 풀이했다.

 

---

소스코드

#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#define MAX 4000001
bool not_prime[MAX];
int sum_prime[MAX/10];
int main(){
    int N;
    scanf("%d", &N);
    int sq = sqrt(N);
    for (int i = 2; i <= sq; i++)
        for (int j = 2*i; j <= N; j += i)
            not_prime[j] = 1;
	
    sum_prime[0] = 0;
    int size = 1;
    for (int i = 2, sum = 0; i <= N; i++)
        if (!not_prime[i])
            sum_prime[size++] = (sum += i);

	
    int left = 0, right = 1, cnt = 0;
    while (left <= right && right < size){
        int temp = sum_prime[right] - sum_prime[left];
        if (temp > N) left++;
        else {
            if (temp == N) cnt++;
            right++;
        }
    }
    printf("%d", cnt);
}

---

출처

1644번: 소수의 연속합