现在的位置: 首页 > 综合 > 正文

LA-3399 & POJ-2739 Sum of Consecutive Prime Numbers 解题报告

2018年04月21日 ⁄ 综合 ⁄ 共 1070字 ⁄ 字号 评论关闭

       素数水题。题意:给你一个不大于一万的整数n,求有多少种方案可以把n写成若干个连续素数的和。


       我的解题思路:把不大于一万的素数都筛出来,存储成前n个素数的和这样的形式。然后枚举每一个方案,把对应方案计算的和所对应的方案次数加一就可以了。存储好一万个数的答案。如果说一万以内的素数个数是k,那么这个枚举的复杂度是O((1+k)*k/2)。也就是k平方的复杂度,时间是够了。0ms水过。


       我的解题代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10002;

bool isprime[N];
int primes[N], pn;
int ans[N];
int n;

void InitRead();

void FastSieve(int maxn);

int main()
{
    InitRead();
    while (~scanf("%d", &n))
    {
        if (n == 0) break;
        printf("%d\n", ans[n]);
    }
    return 0;
}

void InitRead()
{
    memset(isprime, true, sizeof(isprime));
    memset(ans, 0, sizeof(ans));
    isprime[0] = isprime[1] = false;
    pn = 0;
    FastSieve(N - 1);
    int temp[N];    //存储前n个素数的和
    temp[0] = 0;
    for (int i=0; i<pn; ++i)
    {
        temp[i+1] = temp[i] + primes[i];
    }
    for (int i=0; i<pn; ++i)
    {
        for (int j=i+1; j<=pn; ++j) //以primes[i]作为左端点来枚举
        {
            if (temp[j] - temp[i] >= N) break;  //优化一下,如果超过一万了就可以跳出了
            ans[temp[j] - temp[i]]++;
        }
    }
    return;
}

void FastSieve(int maxn)
{
    for (int i=2; i<=maxn; ++i)
    {
        if (isprime[i]) primes[pn++] = i;
        for (int j=0; j<pn; ++j)
        {
            if (i * primes[j] > maxn) break;
            isprime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
    return;
}

抱歉!评论已关闭.