Project Euler——Problem 7 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 6
Project Euler——Problem 8

Project Euler——Problem 7

daybreakcx posted @ 2009年7月17日 21:27 in Prject Euler , 633 阅读

原题与答案:

Problem 7

28 December 2001

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

What is the 10001^(st) prime number?

Answer:104743

 

分析与解答:

这个题目笔算我是没办法了,但是用程序可以很快得到,有一种思路是用试除,但是试除到了后期会有大量的取余运算,时间消耗会不断增长,我写过程序尝试的效果并不是很好,最后决定贴出用筛法做的,基本上结果是瞬出,当然这个数值我曾经做过估计,最早我是用了1000000,结果没想到在110000都不到的时候就出了结果,于是我的程序里面是160000的界,平方也好开。源程序代码如下:

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. const int RANGE=160000;
  4. const int SQRTRANGE=400;
  5. bool nprime[RANGE+1];
  6. int cnt=0,i,j;
  7. int main()
  8. {
  9.         memset(nprime,false,sizeof(nprime));
  10.         for (i=2;i<RANGE;i++)
  11.                 if (!nprime[i])
  12.                 {
  13.                         cnt++;
  14.                         if (cnt==10001) break;
  15.                         if (i<=SQRTRANGE)
  16.                                 for (j=i*i;j<RANGE;j+=i)
  17.                                         nprime[j]=true;
  18.                 }
  19.         printf("%d\n",i);
  20.         return 0;
  21. }

 

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter