hduoj 4715 Difference Between Primes 2013 ACM/ICPC Asia Regional Online —— Warmup
9752 ワード
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
3
6
10
20
Sample Output
11 5
13 3
23 3
Source
2013 ACM/ICPC Asia Regional Online —— Warmup
分析:
この問題は1つの整数を求めて2つの素数(2以上)の差で表し、2つの素数が条件を満たす場合に最小であることを要求する.
ACコード:
View Code
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
3
6
10
20
Sample Output
11 5
13 3
23 3
Source
2013 ACM/ICPC Asia Regional Online —— Warmup
分析:
この問題は1つの整数を求めて2つの素数(2以上)の差で表し、2つの素数が条件を満たす場合に最小であることを要求する.
ACコード:
1 #include <stdio.h>
2 #include <algorithm>
3 #include <iostream>
4 #include <string.h>
5 #include <string>
6 #include <math.h>
7 #include <stdlib.h>
8 #include <queue>
9 #include <stack>
10 #include <set>
11 #include <map>
12 #include <list>
13 #include <iomanip>
14 #include <vector>
15 #pragma comment(linker, "/STACK:1024000000,1024000000")
16 #pragma warning(disable:4786)
17
18 using namespace std;
19
20 const int INF = 0x3f3f3f3f;
21 const int MAX = 1000000 + 10;
22 const double eps = 1e-8;
23 const double PI = acos(-1.0);
24
25 int a[MAX];
26
27 int main()
28 {
29 int i , j ;
30 memset(a , 0 , sizeof(a));
31 a[1] = 1; a[0] = 1;
32 for(i = 2;i <= sqrt(MAX);i++)
33 {
34 if(a[i] == 0)
35 for(j = i * i;j <= MAX;j += i)
36 a[j] = 1;
37 }
38 int n,m;
39 scanf("%d",&n);
40 while(n--)
41 {
42 scanf("%d",&m);
43 int t = abs(m);
44 for(i = t;i < MAX;i++)
45 if(!a[i] && !a[i - t])
46 {
47 if(m > 0)
48 {
49 printf("%d %d
",i,i - t);
50 break;
51 }
52 else
53 {
54 printf("%d %d
",i - t,i);
55 break;
56 }
57 }
58 if(i == MAX)
59 printf("FAIL
");
60 }
61 return 0;
62 }View Code