[BOJ 1644] 소수의 연속합

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

 

풀이 :

 

소수문제입니다.

소수는 항상 에라토스테네스의 체를 사용하시면 됩니다.

 

#include<stdio.h>
 
int n,arr[4000001],s[300000],cnt,ret,sum;
 
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        for (int j = 2; i*j <= n; j++)arr[i*j] = 1;
        if (!arr[i])s[cnt++] = i;
    }
 
    for (int i = cnt - 1; i >= 0; i--) {
        sum = 0;
        for (int j = i; j >= 0&&sum<=n; j--) {
            sum += s[j];
            if (sum == n)ret++;
        }
    }
    printf("%d", ret);
}