/*
Time:2019.11.15
Author: Goven
type:素数 + (艾氏筛法打表)打表 + 尺取法
err:runtime err
ref:https://blog.csdn.net/cc_1012/article/details/88978103
*/
//暴力+runtime err
#include<iostream>
#include<cmath>
using namespace std;
bool a[1005];
int main()
{
for (int i = 2; i < 10001; i++) a[i] = true;
for (int i = 2; i < 10001; i++) {
if (a[i]) {
for (int j = i + 1; j < 10001; j++) {
if (j % i == 0) {
a[j] = false;
}
}
}
}
// for (int i = 3; i < 10001; i++) {
// a[i] = true;
// for (int j = 2; j <= sqrt((double)i); j++) {
// if (i % j == 0) {
// a[i] = false;
// break;
// }
// }
// }
int n, c, sum;
while (cin >> n && n) {
c = 0;
for (int i = n; i >= 2; i--) {
if (a[i]) {
sum = 0;
for (int j = i; j >= 2 && sum < n; j--) {
if (a[j]) {
sum += j;
}
}
if (sum == n) c++;
}
}
cout << c << endl;
}
return 0;
}
//暴力+打表(正确版)
//ref:https://www.jianshu.com/p/09c7c3b48c10
#include<iostream>
#include<cmath>
using namespace std;
bool a[10005];
int b[10005];
int cnt;
int main()
{
for (int i = 2; i < 10001; i++) a[i] = true;
for (int i = 2; i < 10001; i++) {
if (a[i]) {
b[cnt++] = i;
for (int j = i + i; j < 10001; j += i) {
a[j] = false;
}
}
}
int n, c, sum;
while (cin >> n && n) {
c = 0;
for (int i = 0; i < cnt; i++) {
sum = b[i];
int j = i + 1;
while (sum < n && j < cnt) sum += b[j++];
if (sum == n) c++;
}
cout << c << endl;
}
return 0;
}
// 尺取法 核心算法O(n)
//ref:https://blog.csdn.net/cc_1012/article/details/88978103
#include<iostream>
#include<cmath>
using namespace std;
bool a[10005];
int b[10005];
int cnt;
int main()
{
for (int i = 2; i < 10001; i++) a[i] = true;
for (int i = 2; i < 10001; i++) {
if (a[i]) {
b[cnt++] = i;
for (int j = i + i; j < 10001; j += i) {
a[j] = false;
}
}
}
int n, c, sum, s, f;
while (cin >> n && n) {
s = f = sum = c = 0;
while (true) {
if (sum == n) c++;
if (sum > n) sum -= b[s++];
else {
if (b[f] <= n) sum += b[f++];
else break;
}
}
cout << c << endl;
}
return 0;
}
网友评论