首页 > ACM题库 > HDU-杭电 > HDU 4715-Difference Between Primes-数论-[解题报告]HOJ
2015
09-17

HDU 4715-Difference Between Primes-数论-[解题报告]HOJ

Difference Between Primes

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

3
6
10
20

样例输出:

11 5
13 3
23 3

题意:给出一个偶数(不论正负),求出两个素数a,b,能够满足 a-b=x,素数在1e6以内。

只要用筛选法打出素数表,枚举查询下就行了。

我用set储存素数,然后遍历set里面的元素,查询+x后是否还是素数。

注意,偶数有可能是负数,其实负数就是将它正数时的结果颠倒就行了。

代码:

/*
 *  Author:      illuz <iilluzen[at]gmail.com>
 *  Blog:        http://blog.csdn.net/hcbbt
 *  File:        10.cpp
 *  Create Date: 2013-09-08 12:55:09
 *  Descripton:  10 
 */

#include <cstdio>
#include <cmath>
#include <set>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

set<int> m;
#define MAX_P  1000001
int nList[MAX_P] = {0};
void Calc() 
{
	int n,p,t,sq=(int)sqrt(MAX_P*2+1);
	for (n=3;n<=sq;n+=2)
	{
		if (nList[n>>1]) continue;
		for (t=n*n;t<=MAX_P<<1;t+=n<<1) //筛选循环
			nList[t>>1] = 1;
	}
	m.insert(2);
	for (n=t=1;t<MAX_P;++t)
	{
		if (nList[t]) continue;
		m.insert((t<<1)+1);
		if (++n==10)
			n=0;
	}
}
/****** TEMPLATE ENDS ******/

const int MAXN = 0;

int main() {
	Calc();
	int t, n;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		int nn = abs(n);
		bool flag = false;
		for (set<int>::iterator i = m.begin(); i != m.end(); i++) {
			if (m.count(*i + nn) != 0) {
				flag = true;
				if (n < 0) printf("%d %d\n", *i, *i + nn);
				else printf("%d %d\n", *i + nn, *i);
				break;
			}
		}
		if (!flag) printf("FAIL\n");
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/hcbbt/article/details/11402641