POJ 2739 素数打表

简介:

题意:给你一个数问你用连续的素数来表示这个数有几种表示方法。

先打一个素数表,再把素数表变下形,prime[i]存prime[i]之前的素数和,循环一下打出ans表即可。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 10050
int prime[maxn],nprime,ans[maxn];
bool isprime[maxn];
void getprime()
{
    memset(isprime,1,sizeof(isprime));
    nprime=0;
    long long i,j;
    for(i=2; i<maxn; i++)
        if(isprime[i])
        {
            prime[++nprime]=i;
            for(j=i*i; j<maxn; j+=i)
                isprime[j]=0;
        }
}
int main()
{
    getprime();
    prime[0]=0;
    memset(ans,0,sizeof(ans));
    for(int i=2; i<=nprime; i++)
        prime[i]=prime[i]+prime[i-1];
    for(int i=0; i<=nprime; i++)
        for(int j=i+1; j<=nprime; j++)
            if(prime[j]-prime[i]<maxn)
                ans[prime[j]-prime[i]]++;
            else
                break;
    int n;
    while(~scanf("%d",&n),n)
        printf("%d\n",ans[n]);
    return 0;
}


目录
相关文章
|
6月前
|
算法
Wormholes—POJ3259
Wormholes—POJ3259
|
存储
POJ 1012 Joseph
Joseph Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 53862   Accepted: 20551 Description The Joseph's problem is notoriously known.
841 0
POJ 1067 取石子游戏
取石子游戏 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 40917   Accepted: 13826 Description 有两堆石子,数量任意,可以不同。
1112 0
poj 3664
http://poj.org/problem?id=3664 进行两轮选举,第一轮选前n进入第二轮,第二轮选最高   #include #include using namespace std; struct vote { int a,b; int c; ...
735 0
|
算法 数据建模 机器学习/深度学习
|
JavaScript