Chinaunix首页 | 论坛 | 博客
  • 博客访问: 237985
  • 博文数量: 47
  • 博客积分: 1229
  • 博客等级: 中尉
  • 技术积分: 568
  • 用 户 组: 普通用户
  • 注册时间: 2010-09-20 10:06
文章分类

全部博文(47)

文章存档

2014年(1)

2013年(7)

2012年(1)

2011年(38)

分类: C/C++

2011-03-02 23:35:20

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <limits.h>
  5. #include <math.h>

  6. #define NUM    10001
  7. int prime[NUM];

  8. #if 0
  9. int is_prime(int num)
  10. {
  11.     int i;

  12.     int sqrt_num = 1+sqrt(num);
  13.     for (i = 3; i < sqrt_num; i+=2) {
  14.         if (!(num%i))
  15.             return 0;
  16.     }

  17.     return 1;
  18. }

  19. #else
  20. int is_prime(int num)
  21. {
  22.     int i;
  23.     int sqrt_num = sqrt(num);

  24.     for (i = 0; i < NUM; i++) {
  25.         if (prime[i]) {
  26.             if (!(num % prime[i]))
  27.                 return 0;
  28.             else if (prime[i] > sqrt_num)
  29.                 break;

  30.         } else
  31.             break;
  32.     }

  33.     return 1;
  34. }
  35. #endif

  36. int main(int argc, const char *argv[])
  37. {
  38.     int nr = 2;
  39.     int i;

  40.     memset(prime, 0, sizeof(prime));
  41.     prime[0] = 2;
  42.     prime[1] = 3;
  43.     
  44.     for (i = 5; i < (INT_MAX); i+=2) {
  45.         if (is_prime(i)) {
  46.             prime[nr] = i;
  47.             if (++nr == NUM)
  48.                 break;

  49.         }
  50.     }

  51.     printf("result: %d\n", i);

  52.     return 0;
  53. }
阅读(1061) | 评论(0) | 转发(0) |
0

上一篇:euler5

下一篇:euler8

给主人留下些什么吧!~~