第七解:

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的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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重新实现了一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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会更快:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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就那么难解,下面是用递归实现的程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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秒就出了结果,说到底,算法的改进才是硬道理!