hdu4715Difference Between Primes

Difference Between Primes

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 894Accepted Submission(s): 290

Problem Description

All you know Goldbach conjecture.That is to say, Every even integer greater than 2 can be expressed as the sum of two primes. Today, skywind present a new conjecture: every even integer can be expressed as the difference of two primes. To validate this conjecture, you are asked to write a program.

Input

The first line of input is a number nidentified the count of test cases(n<10^5). There is a even number xat the next nlines. The absolute value of xis not greater than 10^6.

Output

For each number xtested, outputstwo primes aand bat one line separatedwith one space where a-b=x. If more than one group can meet it, output the minimum group. If no primes can satisfy it, output 'FAIL'.

Sample Input

3
6
10
20

Sample Output

11 5
13 3
23 3

Source

2013 ACM/ICPC Asia Regional Online —— Warmup

Recommend

liuyiding

题解：

刚接触这种题时我是以为数据规模一定很大，一般的枚举或者就算是剪枝也应该通过不了，应该是要推导出什么公式。。然后就没做。。。。

可是没想到~~~还是要多尝试。。尝试之后就会发现很多都和想的不同。。。

所以我就枚举

用isprime【】数组来存下标i时是否为质数

用prime【】来保存质数{2，3,，5，7,11……}；

这就是为了打表

因为它的测试数据可以有10^5次

打表是必须的~~~

然后到了枚举。。枚举也是有技巧的。

枚举是要这样枚举。。枚举质数{2,3,5,7,11……}

这样可以省很多没用的操作。。。

还有就是输入的数可以是负数的。。。我在这里wa了几次

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int prime[10002];
bool isprime[100902];
int n;
bool isnotprime(int a)
{
	int m = (int)sqrt((double)a) + 1;
	for(int i=2;i<=m;i++)
	{
		if(a%i == 0)
		{
			return false;
		}
	}
	return true;
}
int main()
{
	int T,i,j;
	int flag;
	prime[0] = 2, prime[1] = 3;
	isprime[0] = isprime[1] = isprime[4] = false;
	isprime[2] = isprime[3] = true;
	i = 2;
	for(int t=5;t<100901;t++)
	{
		isprime[t] = isnotprime(t);
		if(isprime[t])
		prime[i++] = t;
	}
	//memset(prime,true,sizeof(prime));
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		if(n>0)
			flag = 1;
		else
			flag = 0;
		n = abs(n);
		int num = i;
		for(j=0;j<num;j++)
		{
			if(isprime[n+prime[j]])
				break;
		}
		if(j == num)
		{
			printf("FAIL\n");
			continue;
		}
		if(flag == 1)
		printf("%d %d\n",n+prime[j],prime[j]);
		else
			printf("%d %d\n",prime[j],n+prime[j]);
		
	}
	return 0;
}

不过遗憾的是。我不能计算出最多只需要计算出多少质数，就是isprime【】和prime【】要定义多大

不然又可以省很多时间。。。。