北邮ACM2017热身赛-D题

题目

分析

给定一个整数，将它分解成连续素数的和，求这样的分解方法数

思路

先利用素数筛打出素数表

然后

代码

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include <vector>
using namespace std;

vector<int> primes;
bool is_prime[1000006];

//建立素数表和存储素数的vector
void init_primes()
{
    memset(is_prime,true, 1000005);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= 1000005; ++i){
        if (is_prime[i]){
            primes.push_back(i);
            for (int j = 2; j*i <= 1000005; j++){
                is_prime[i*j] = false;
            }
        }
    }
}
 
int main(){
    vector<int> output;
    init_primes();
    int primesnum = primes.size();
    int n;
    while (cin >> n){
        //i是分解形式的首个素数，j是最后一个素数
        int i = 0, j = 0, sum = 0, result = 0;
        while(true){
            while (sum < n && j < primesnum){
                sum += primes[j++];
            }
            //加到最后一个素数了，和还是小于n，说明后面没有满足条件的分解方式了，跳出循环结束运算
            if (sum < n){
                break;
            }
            else if (sum == n){
                ++result;
            }
            //i向后移
            sum -= primes[i++];
        }
        output.push_back(result);
    }
 
    for (int i = 0; i < output.size(); i++) {
        cout << output[i] << endl;
    }
    //system("pause");
    return 0;
}