백준 1644번 문제 ( 소수의 연속합 )

문제 출처 : https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

이 문제는 에라토스테네스의 체와 투 포인터를 사용하는 것인데 투 포인터 개념을 아직 숙지하지 못해 가볍게 풀어보았다. 

에라토스테네스 체를 이용하여서 소수를 구하고 소수를 완전탐색으로 모든 조건을 계산하여서 해결하였다.

아래는 해당 문제를 풀이한 소스이다.

#include<stdio.h>
#pragma warning(disable:4996)
int arr[4000001];
int sosu[4000001];
int sosu_index = 0;
void make_sosu(int n)
{
    arr[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (arr[i] == 1)
            continue;
        for (int j = 2; i * j <= n; j++)
            arr[i * j] = 1;
    }
    for (int i = 2; i <= n; i++)
    {
        if (arr[i] == 0)
        {
            sosu[sosu_index] = i;
            sosu_index++;
        }
    }
}
int main()
{
    int num;
    scanf("%d", &num);
    make_sosu(num);
    int sum = 0;
    int count = 0;
 
    for (int i = 0; i < sosu_index; i++)
    {
        for (int j = i; j < sosu_index; j++)
        {
            if (sum < num)
                sum = sum + sosu[j];
            if (sum > num)
            {
                sum = 0;
                break;
            }
            if (sum == num)
            {
                count++;
                sum = 0;
                break;
            }
        }
    }
    printf("%d", count);
}