poj2739 素数 + 打表 + 尺取法

 /*
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;
}