黑马程序员技术交流社区

标题: 哥德巴赫猜想的程序实现 [打印本页]
作者: gxppq    时间: 2014-12-21 20:09
标题: 哥德巴赫猜想的程序实现
2000以内的正偶数都能够分解为两个素数之和(即验证歌德巴赫猜想对2000以内的正偶数成立)。
  1. #include<stdio.h>
  2. #include<math.h>
  3. int fflag(int n);
  4. void main()
  5. {
  6.         int i,n;
  7.         for(i=4;i<=2000;i+=2)
  8.         {
  9.                 for(n=2;n<i;n++) /*将偶数i分解为两个整数*/
  10.                         if(fflag(n)) /*分别判断两个整数是否均为素数*/
  11.                         if(fflag(i-n))
  12.                         {
  13.                                 printf("%14d=%d+%d\n",i,n,i-n); /*若均是素数则输出*/
  14.                                 break;
  15.                         }
  16.                         if(n==i) printf("error %d\n",i);
  17.         }
  18. }
  19. int fflag(int i) /*判断是否为素数*/
  20. {
  21.         int j;
  22.         if(i<=1)return 0;
  23.         if(i==2)return 1;
  24.         if(!(i%2))return 0; /*if no,return 0*/
  25.         for(j=3;j<=(int)(sqrt((double)i)+1);j+=2)
  26.         if(!(i%j))return 0;
  27.         return 1; /*if yes,return 1*/
  28. }
复制代码

程序中证明一个整数n是否为素数的调用函数fflag的算法是：如果n不能被2到根号n之间的整数整除，那么n就是素数。因为如果一个能被一个大于根号n的整数整除，那么商肯定小于根号n，所以也能被小于根号n整除，因此只要不能被小于根号n的整数整除，就一定不能被大于根号n的整数整除，只需要验证到根号n就可以。
作者: 小平    时间: 2014-12-21 20:31
同学们好！



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2