45 lines
978 B
C
45 lines
978 B
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <stdbool.h>
|
|
|
|
int main() {
|
|
int N;
|
|
scanf("%d",&N);
|
|
|
|
bool* isPrime = (bool*)malloc(sizeof(bool)*(N+1));
|
|
|
|
for(int i=0; i<=N; i++) isPrime[i] = (i==0 || i==1) ? false : true;
|
|
|
|
for(int i=2; i*i<=N; i++) {
|
|
if(isPrime[i]) {
|
|
for(int j=i*i; j<=N; j+=i) {
|
|
isPrime[j] = false;
|
|
}
|
|
}
|
|
}
|
|
|
|
int prime_count = 0;
|
|
for(int i=0; i<=N; i++) if(isPrime[i]) prime_count++;
|
|
int* primes = (int*)malloc(sizeof(int)*(prime_count));
|
|
int idx=0;
|
|
for(int i=2; i<=N; i++) if(isPrime[i]) primes[idx++] = i;
|
|
|
|
int start = 0, end = 0;
|
|
int current_sum = 0;
|
|
int result = 0;
|
|
|
|
while(start < prime_count) {
|
|
while(end < prime_count && current_sum < N) current_sum += primes[end++];
|
|
|
|
if(current_sum == N) result++;
|
|
|
|
current_sum -= primes[start++];
|
|
}
|
|
|
|
printf("%d\n",result);
|
|
|
|
free(isPrime);
|
|
free(primes);
|
|
|
|
return 0;
|
|
} |