POJ 2739 素数打表+暴力枚举

发表于 | 分类于 | 阅读次数:
字数统计: 282 字

题目连接：http://poj.org/problem?id=2739

题意

给出一个数，问其有多少种方案能够分解成连续多个素数的和

题解

因为这道题的数据规模只有10000所以完全可以暴力解决，首先使用欧拉筛选得到素数表，枚举所有在数据范围内的连续素数和，打表。

代码

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
37
38
39
40
41
42
43
44
45
46
const int maxp=10005;
bool is_prime[maxp];
int prime[maxp],num;
int a[maxp];

void init()    //欧拉筛选素数打表
{
	num=0;
    memset(is_prime,true,sizeof(is_prime));
	is_prime[0]=is_prime[1]=false;
	for(int i=2;i<maxp;i++)
	{
		if(is_prime[i]) prime[num++]=i;
		for(int j=0;j<num && i*prime[j]<maxp;j++)
		{
			is_prime[i*prime[j]]=false;
			if(i%prime[j]==0) break;
		}
	}
}

void fun()  //枚举所有的连续素数和，打表
{
	memset(a,0,sizeof(a));
	int tmp;
	for(int i=0;i<num;i++)
		for(int j=i;j<num;j++)
		{
			tmp=0;
			for(int k=i;k<=j;k++)
				tmp+=prime[k];
			if(tmp<maxp)
				a[tmp]++;
		}
}

void solve()
{
	int t;
	init();
	fun();
	while(scanf("%d",&t)!=EOF && t)
	{
		printf("%d\n",a[t]);
	}
}