Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2968935
  • 博文数量: 272
  • 博客积分: 5544
  • 博客等级: 大校
  • 技术积分: 5496
  • 用 户 组: 普通用户
  • 注册时间: 2011-03-08 00:48
个人简介

  每个人都要有一个骨灰级的爱好,不为金钱,而纯粹是为了在这个领域享受追寻真理的快乐。

文章分类

全部博文(272)

文章存档

2015年(2)

2014年(5)

2013年(25)

2012年(58)

2011年(182)

分类: LINUX

2013-02-24 00:53:04

原帖在此处


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <time.h>

  5. void create_prime (char *s, int **prime, int n, int *prime_len) {
  6.     int i, j, _len, max;
  7.     int *_prime;

  8.     max=(int)sqrt((double)n);
  9.     while (max * max <= n)
  10.         max++;
  11.     max--;


  12.     /* 初始化s数组,全部写零 */
  13.     for (i=0; i<n; i++)    s[i] = 0;

  14.     /*
  15.     除1以外的数都分为质数和合数
  16.     除2以外的偶数都是合数, 质数只可能存在于奇数中
  17.     所以把3到sqrt(n)之内的质数求出
  18.     (如果n是合数, 必然有一个约数是大于1而小于等于它的平方根)
  19.     该奇数的倍数都是合数,打上标记1.剩下的奇数则都为质数.
  20.     比如36的平方根为6, 那么除3和5的倍数以外的奇数则都为质数(也包含了1和2).
  21.     */

  22.     //从3开始遍历到max的奇数
  23.     for (i=3; i<=max; i+=2)
  24.         if(s[i] == 0)
  25.             //从6开始,把质数的倍数标记为1(它们都是合数)
  26.             for(j=i*i; j<=n; j+=i*2)
  27.                 s[j]=1;

  28.     *prime_len = 0;
  29.     _len = 10000;
  30.     if ((_prime = malloc(sizeof(int) * _len)) == NULL) {
  31.         fprintf(stderr, "malloc failed\n");
  32.         exit(1);
  33.     }
  34.     for (i=3; i<=n; i+=2) {//把所有质数存入数组
  35.         if (s[i] == 0) { //如果是质数
  36.             if (*prime_len >= _len) { //判断动态内存是否足够
  37.                 _len += 10000;
  38.                 _prime = realloc(_prime, sizeof(int) * _len);
  39.             }
  40.             _prime[*prime_len] = i;
  41.             *prime_len += 1; //prime_len为质数的数量
  42.         }
  43.     }
  44.     *prime = _prime;
  45. }

  46. int check (char *s, int *prime, int n, int prime_len) {
  47.     int i, j, flag;

  48.     //遍历所有大于2的偶数
  49.     //因为哥德巴赫猜想是求大于2的偶数
  50.     for (i=4; i<=n; i+=2) {
  51.         flag = 0;
  52.         //j < prime_len 保证不越界超过质数的数量范围
  53.         //i > prime[j] 确保相减不是一个负数
  54.         for (j=0; j<prime_len && i>prime[j]; j++) {
  55.             //从我们的质数表prime[0]开始
  56.             //如果i - prime[j]也是一个质数,则偶数i就是两个质数的和
  57.             //哥德巴赫猜想成立
  58.             if (s[i-prime[j]] == 0) {
  59.                 flag = 1;
  60.                 break;
  61.             }
  62.         }
  63.         if(flag == 0)    return -1;
  64.     }

  65.     return 0;
  66. }

  67. int main(int argc, char **argv) {
  68.     int n, prime_len;
  69.     int *prime;
  70.     char *s;

  71.     time_t t = time(NULL);
  72.     if (argc < 2) {
  73.         printf("Please type the range\n");
  74.         exit(-1);
  75.     }
  76.     n = atoi(argv[1]);
  77.     if((s = (char *)malloc(n)) == NULL) {
  78.         fprintf(stderr, "malloc failed\n");
  79.         return 1;
  80.     }

  81.     create_prime(s, &prime, n, &prime_len);

  82.     if(check(s, prime, n, prime_len) == 0)
  83.         t = time(NULL) - t;
  84.         printf("in the range 4 - %d, Goldbach conjecture was established.\nit takes %ld seconds.\n", n, t);

  85.     return 0;
  86. }



不足之处欢迎拍砖, 感谢cjaizss.

本程序利用的筛法, 申请两块内存区域, 一个状态机, 一个质数表, 指针s指向的内存区域为n个字节, 初始化为0, 把0到n个数种的合数筛选出来, 在数组s中设置为1, 再求出状态机为0的即为质数(包括1和2,非合数也非质数), 存放进数组prime中, 遍历检查的时候, 就用偶数n减去质数表内的质数, 把结果放入状态机中看是否值为0, 如果为0那么也是一个质数, 则哥德巴赫猜想成立, 跳出循环, 检查下一个偶数.




阅读(2778) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~