首页 > 代码库 > 素数筛选 HDU 4715

素数筛选 HDU 4715

2024-08-04 04:44:43   217人阅读

打表，把所有的素数找出来，并且还要把那些数是素数标记下

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
3
6
10
20
 

Sample Output
11 5
13 3
23 3
 

Source
2013 ACM/ICPC Asia Regional Online —— Warmup
 
#include <iostream>
#include <stdio.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include<string>
#include <queue>
#include<map>
#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; j<primenum; j++)
	if (i%prime[j] == 0)break;
	else if (prime[j]>sqrt((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;
}


素数筛选 HDU 4715


联系
我们