程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 素數篩選 HDU 4715

素數篩選 HDU 4715

編輯：C++入門知識

素數篩選 HDU 4715

打表，把所有的素數找出來，並且還要把那些數是素數標記下

Difference Between Primes

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

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

Sample Output

11 5
13 3
23 3

Source 2013 ACM/ICPC Asia Regional Online —— Warmup

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include
#define ll long long
#define N 1000010
#define eps 1e-6
#define pi acos(-1.0)
using namespace std;
const int INF = (1 << 30);

bool isprime[N];
int prime[N], primenum;//有primenum個素數 math.h
void PRIME(){
	primenum = 0;
	memset(isprime, false, sizeof(isprime));
	isprime[2] = true;
	prime[primenum++] = 2;
	for (int i = 3; i < N; i += 2)
	for (int j = 0; jsqrt((double)i) || j == primenum - 1)
	{
		prime[primenum++] = i;
		isprime[i] = true;
		break;
	}
}
int main()
{
	PRIME();
	int t, n;
	cin >> t;
	while (t--)
	{
		cin >> n;
		int flag = 0;
		for (int i = 0; i < primenum; i++)
		{
			if (prime[i] > n && isprime[prime[i] - n])
			{
				flag = 1;
				printf("%d %d\n", prime[i], prime[i] - n);
				break;
			}
		}
		if (!flag)
			puts("FAIL");
	}
	return 0;
}