Project Euler——Problem 7

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

原题与答案：

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的界，平方也好开。源程序代码如下：

#include<stdio.h>
#include<string.h>
const int RANGE=160000;
const int SQRTRANGE=400;
bool nprime[RANGE+1];
int cnt=0,i,j;
int main()
{
memset(nprime,false,sizeof(nprime));
for (i=2;i<RANGE;i++)
if (!nprime[i])
{
cnt++;
if (cnt==10001) break;
if (i<=SQRTRANGE)
for (j=i*i;j<RANGE;j+=i)
nprime[j]=true;
}
printf("%d\n",i);
return 0;
}