欧拉工程第七解

| Comments

第七解:

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