算法竞赛入门经典chapter4:4-1孪生素数

时间:2024-03-11 22:35:35

如果n和n+2都是素数,则称他们是孪生素数。输入m,输出连个数均不超过m的最大孪生素数。5<=m<=10000.例如m=20时的答案是17、19,m=1000时的答案是881、883.

Code
 1 #include<iostream>
 2 #include<cmath>
 3 #include<assert.h>
 4 using namespace std;
 5 /*
 6 bool is_primer(int x)
 7 {
 8     for(int i = 2; i*i <= x; ++i)   //中间值可能会溢出
 9         if(x%i == 0)    return false;
10     return true;
11 }
12 */
13 //建议把谓词(用来判断某事物是否具有某种特性的函数)命名成“is_xxx”的形式。
14 //编写函数时,应尽量保证它能对任何合法参数都能得到正确的结果。如若不然,
15 //应在显著位置标明函数的缺陷,以避免误用
16 //--------------------------改进之后----------------------------
17 bool is_primer(int x)
18 {
19     //被1和它本身整除的、大于1的整数称为素数。
20     assert(x >= 0);//用assert宏来限制非法的函数调用:当x>=0不成立时,程序就将异常终止,
21     //并给出提示信息。检查非法参数是很有用的:当算法很复杂时,一不小心就会用非法参数
22     //调用默写自定义函数,如果函数不对参数进行检查,则很可能让整个程序得到一个荒唐的
23     //结果。如果函数调用关系非常复杂,是难以查处错误的根源的。如果每个函数都检查参数,
24     //就能较快地找出“罪魁祸首”
25     int m = floor(sqrt(x)+0.5);//使用变量m,避免重复计算sqrt(n),另一方方面也通过
26     //四舍五入避免了浮点误差-如果sqrt“不小心”吧某个本应该是整数的值弄成了xxx.99999,
27     //也将被修正,但直接些m=sqrt(x)的话那个“.99999”会被无情的截掉。
28     //#include <math.h>  double floor( double arg );floor函数返回参数不大于arg的最大整数
29     if(x == 1)  return false;
30     for(int i = 2; i<= m; ++i)
31     {
32         if(x%i==0)
33             return false;
34     }
35     return true;
36 }
37 int main()
38 {
39     int m;
40     while(cin >> m)
41     {
42         for(int i = m-2; i >= 3; --i)
43         {
44             if(is_primer(i) && is_primer(i+2))
45             {
46                 cout << i << "" << i+2 << endl;
47                 break;
48             }
49         }
50     }
51     return 0;
52 }
53 
54 //编译时合理地利用assert宏,讲给调试带来很大的方便。是编写的程序质量更高。