http://acm.hdu.edu.cn/showproblem.php?pid=4715

Difference Between Primes

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

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 x at the next n lines. The absolute value of x is not greater than 10^6.

Output

For each number x tested, outputs two primes a and b at one line separated with 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

分析：

这道题就是求一个整数用两个素数（大于等于2）的差表示出来，要求两个素数在满足条件的情况下最小。

AC代码：

 #include <stdio.h>

 #include <algorithm>

 #include <iostream>

 #include <string.h>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <queue>

 #include <stack>

 #include <set>

 #include <map>

 #include <list>

 #include <iomanip>

 #include <vector>

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #pragma warning(disable:4786)

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int MAX =  + ;

 const double eps = 1e-;

 const double PI = acos(-1.0);

 int a[MAX];

 int main()

 {

     int i , j ;

     memset(a ,  , sizeof(a));

     a[] = ; a[] = ;

     for(i = ;i <= sqrt(MAX);i++)

     {

         if(a[i] == )

             for(j = i * i;j <= MAX;j += i)

                 a[j] = ;

     }

     int n,m;

     scanf("%d",&n);

     while(n--)

     {

         scanf("%d",&m);

         int t = abs(m);

         for(i = t;i < MAX;i++)

             if(!a[i] && !a[i - t])

             {

                 if(m > )

                 {

                     printf("%d %d\n",i,i - t);

                     break;

                 }

                 else

                 {

                     printf("%d %d\n",i - t,i);

                     break;

                 }

             }

         if(i == MAX)

             printf("FAIL\n");

     }

     return ;

 }

巴特西

hduoj 4715 Difference Between Primes 2013 ACM/ICPC Asia Regional Online —— Warmup

Difference Between Primes

最新文章

热门文章