首页 > 代码库 > POJ 1007 Difference Between Primes（线性筛法求N以内的素数表）

POJ 1007 Difference Between Primes（线性筛法求N以内的素数表）

2024-07-16 16:09:00   223人阅读



 Difference Between Primes
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

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
 

题目大意：

输入一个偶数，求满足素数相减得到这个偶数的最小的两个素数（注意绝对值）。

解题思路：

先打素数表。


代码：

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
using namespace std;

const int maxn=1000000;
map<int,int> mymap;
int prime[maxn],isPrime[maxn];

int main(){
    int temp,b,i,n,j,flag,total=0;//total表示质数的个数，prime[total]表示第几个质数是多少.
    memset(isPrime,0,sizeof(isPrime));//一般来讲，memset只是用来填充单个字节的(比如char)或者填充0,所以暂且把值为0看作素数吧。
    for(i=2;i<=maxn;i++){
        if(isPrime[i]==0) {prime[total++]=i; mymap[i]=1;}//把质数i放进map。
            for(int j=0;j<total&&i*prime[j]<=maxn;j++){
                isPrime[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
    }
    scanf("%d",&n);
    while(n-->0){
        scanf("%d",&b);
        temp=b;flag=1;
        if(temp<0) temp=-temp;
        for(i=2;i<=maxn;i++){
            if(mymap[i]==1&&mymap[i+temp]==1){
                if(b>0)
                printf("%d %d\n",i+temp,i);
                else
                printf("%d %d\n",i,i+temp);
                flag=0;
                break;
            }
        }
        if(flag==1)
            printf("FAIL\n");//664579.
    }
    return 0;
}





联系
我们