Difference Between Primes

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

题意：给一个偶数，将这个偶数用两个最小的素数表示，如果不能表示则输出FALL; 注意给定的偶数可能为负值。

思路：素数打表，将给定的数从第一个素数开始相加，判断相加后的值是否为素数。

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 const int N=1000050;
 5 int f[N],p[N/2];
 6 int num;//1e6内素数个数
 7 
 8 void is_prime()
 9 {
10     f[1] = 0;
11     f[2] = 1;
12     for (int i = 3; i < N; i ++)
13     {
14         f[i] = i%2;
15     }
16     for (int i = 3; i*i < N; i ++)
17     {
18         if (f[i])
19         {
20             for (int j = 2*i; j < N; j += i)
21                 f[j] = 0;
22         }
23     }
24     num = 0;
25     for (int i = 2; i < N; i ++)
26     {
27         if(f[i]) p[num++] = i;
28     }
29 }
30 int main()
31 {
32     int t;
33     memset(f,0,sizeof(f));
34     scanf("%d",&t);
35     is_prime();
36     while(t--)
37     {
38         int m,i,flag = 0;
39         scanf("%d",&m);
40         if (m < 0)
41         {
42             flag = 1;
43             m = -m;
44         }
45         for (i = 0; i < num; i++)
46         {
47             int x = p[i];
48             if(f[x+m])
49             {
50                 if (!flag)
51                     printf("%d %d
",m+x,x);
52                 else
53                     printf("%d %d
",x,m+x);
54                 break;
55             }
56         }
57         if (i >= num)
58             printf("FAIL
");
59     }
60     return 0;
61 }

View Code