Algoogle

Algorithm for Programming Contest

AOJ 1257 Sum of Consecutive prime Numbers

Category: AOJ Tag: inchworm-method, math

Sum of Consecutive prime Numbers

問題概要


解法


連続した素数の和を考えるということなのでしゃくとり法で見ていきます.
右の数がNを超えるか, 左右の位置が一致したら終了.

コード


(1257.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define rep(i,a) for(int i = 0;i < (a); i++)
#define pb push_back
using namespace std;
typedef vector<int> vi;

bool p[10010];
vi prm;

void pcalc(){
    rep(i,10010) p[i] = (i < 2)? false: true;
    rep(i,10010)if(p[i]){
        prm.pb(i);
        for(int j = i*2; j < 10010; j += i) p[j] = false;
    }
}

int main(){
    pcalc();
    int n;
    while(cin >> n, n){
        int left = 0, right = 0, sum = 2;
        int ans = 0;
        do{
            if(sum > n) sum -= prm[left++];
            if(sum < n) sum += prm[++right];
            if(sum == n) {
                ans++;
                sum -= prm[left++];
            }
        }while(prm[right] <= n && left != right);

        cout << ans << endl;
    }
    return 0;
}

Comments