[C언어] 백준 | 1644번 소수의 연속합

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

1644번: 소수의 연속합

안녕하세요, 골드 3을 우연찮게 풀게 됐습니다. 투포인터를 배우자마자 처음으로 푼 문제입니다.

연속합 문제라 투포인터를 사용하면 쉽게 풀 수 있는 문제인데, 에라토스테네스의 체를 사용해야 합니다. 

왜냐면 소수의 연속합 문제이기 때문이죠. 

 

에라토스테네스의 체는 예전에 풀어봐서 구현은 쉽게 했습니다.

하지만 문제가 있었습니다. N이 400만이었기 때문인데요, 지역 변수로 400만개짜리 배열을 선언했더니 zsh segmentation fault였나? 오류가 떴습니다. 100만 정도까진 괜찮았는데 좀 커지면 계속 오류가 뜨더라고요.

그래서 전역 변수로 배열을 선언해줌으로써 문제를 해결했습니다. 하지만 고작 그것 하나 해결하는 데에 20분 가까이 썼다는 점이 아쉬웠습니다.

 

하지만 지식을 얻었다는 것.

그렇다면 오케이겠죠?

 

brr의 사이즈가 283148인 이유는 1~400만 사이의 소수의 개수가 283148개였나? 그쯤이길래 저렇게 했습니다.

 

#include <stdio.h>
#include <math.h>

#define S 4000001 //배열 크기
int arr[S] = {0};

int main(void) {
    int brr[283148];
    int n = 1, N;
    int a = 1, b = 2, temp, answer = 0;
    scanf("%d", &N);

    for(int i = 2; i < sqrt(S); i++) { //에라토스테네스의 체
        if(arr[i] != 1) {
            for(int j = 2; i * j < S; j++) {
                arr[i * j] = 1;
            }
        }
    }
    for(int i = 2; i <= S; i++) { //소수를 brr로 옮기기
        if(arr[i] != 1) {
            brr[n] = i;
            n++;
        }
    }
    temp = brr[1];
    for(int i = 1; i < 283148 * 2; i++) { //여기서부터 투포인터 입니다.
        if (temp < N) {
            temp += brr[b];
            b++;     
        }
        else if(temp > N) {
            temp -= brr[a];
            a++;    
        }
        else if(temp == N) {
            answer++;
            temp += brr[b];
            b++;   
        }
        if(brr[b - 1] > N) break;
    }
    printf("%d", answer);
}

400만을 여러 번 적으려니까 귀찮아져서 define 사용해봤습니다. 

하하하 감사합니다