🌚

# 欧拉工程第七解

Posted at — Oct 31, 2008

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?

```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 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; ```

```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) ```

```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秒就出了结果，说到底，算法的改进才是硬道理！