第七解：
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?
穷举，并加以最大程度的优化：对大于2的素数，只判断奇数；判断一个奇数是否素数时，只拿已经找到的素数中小于第这个数平方根的数来相除，如果均不能整除，就是素数。Python的实现：
```python def IsPrimeNum(num,feed): from math import sqrt tmp = feed[:] while tmp[-1] > int(sqrt(num)): tmp.pop() for i in tmp: if num % i == 0: return False return True limit = 10001 feed = [2,3,5,7] temp = 7 counter = 4 while counter < limit : temp += 2 if IsPrimeNum(temp,feed): feed.append(temp) counter += 1 print temp ```
执行了一下，在我这里居然用了五百秒才出结果，神啊，差不多十分钟啊。想到PHP号称速度很快，于是用PHP重新实现了一下：
```php function IsPrimeNum($num,$feed){ $base = floor(sqrt($num)); foreach($feed as $i=>$v){ if($v > $base){ return true; } if($num % $v == 0){ return false; } } } $limit = 10001; $feed = array(2,3,5,7); $counter = 4; $tmp = 7; while($counter < $limit){ $tmp += 2; if(IsPrimeNum($tmp,$feed)){ $counter++; $feed[] = $tmp; } } echo $tmp; ```
还好，七十四秒出结果，看来PHP的牛皮不是吹的。当然，Lua会更快：
```lua function IsPrimeNum(num,feed) require('math') local limit = math.floor(math.sqrt(num)) for i,v in ipairs(feed) do if v > limit then return true end if num % v == 0 then return false end end end local limit = 10001 local feed = {2,3,5,7} local counter = 4 local tmp = 7 while counter < limit do tmp = tmp + 2 if IsPrimeNum(tmp,feed) then counter = counter + 1 table.insert(feed,tmp) end end print(tmp) ```
执行完后还是吓了一跳，0.3秒，同样是语言，效率的差别咋就那么大呢？！我在想用Java会不会算到2009去。
我不相信这道题用Python就那么难解，下面是用递归实现的程序：
```python from math import sqrt def GuessPrime(feed,limit): if feed == 2 : return [2] elif feed == 3 : return [2,3] tmp = int(sqrt(feed)) primes = GuessPrime(tmp,limit) base = 0 if tmp % 2 == 0: base = tmp + 1 else: base = tmp for i in range(base,feed,2): flag = 0 for j in primes: if i % j == 0: flag = 1 break if flag == 0: primes.append(i) if len(primes) == limit: return primes return primes limit = 10001 feed = 1000000 primes = GuessPrime(feed,limit) print primes[limit-1] ```
11秒就出了结果，说到底，算法的改进才是硬道理！
