poj2739解题报告

时间：2010-07-18 来源：godfrey90

1.算法
通过筛法找出10000以内所有的素数，存到数组里。然后对每个输入的数num，尝试用连续的比num小的素数，用num减去这个这些连续的素数，如果结果是零，则在结果上加上1，最后输出结果。
2.实现
(1)对于数组初始化的时候，int a[10]={1}只能对数组的第一个字符进行初始化，但是int a[10]={0}可将整个数组进行初始化。关于c++中数组初始化，具体参见http://hi.baidu.com/sicceer/blog/item/a1f3ba54dc87fb133a293595.html
(2)注意在函数传参数的时候的指针和引用的用法。
3.代码：

#include<cstdio>

void creat_primes(int* prime,int& size);
int calculate(int* prime,int size,int num);

int main()
{
int prime[10000];
int size_of_primes = 0 ;
//生成素数表
creat_primes(prime,size_of_primes);
//读取和计算
int num = 0;
scanf("%d",&num);
while(num!=0)
{
if(int result = calculate(prime,size_of_primes,num))printf("%d\n",result);
else printf("0\n");
scanf("%d",&num);
}
return 0 ;
}
/*生成一个素数表*/
void creat_primes(int* prime,int& size)
{
int notPrime[10001] = {false};
for (int i = 2;i<10001;i++)
{
int x = i*2;
while(x<10001)
{
notPrime[x]=true;
x+=i;
}
}
for(int i=2;i<10001;i++)
{
if(!notPrime[i]) prime[size++]=i;
}
}
/*计算这个num有几种表现方式*/
int calculate(int* prime,int size,int num)
{
int result = 0;
for(int i = 0;i<size;i++)
{
if (prime[i]>num) break;
int n = num;
int index = i;
while(n>0)
{
n-=prime[index];
index++;
}
if (n==0)result++;
}
return result;
}

相关阅读更多 +