Mayx的博客

Logo

Mayx's Home Page

View My GitHub Profile

About Me
21 October 2019 - 字数统计:1350 - 阅读大约需要4分钟 - Hits: Loading...

Python学习笔记 - 求质数

by mayx


讲真,我酸了……

起因

在学习Python的过程中,我和同学举行了一个比赛,大概内容是用Python做一个时间复杂度最低的质数生成器。
在学校里就是有个好处,学校网络上知网下论文是免费的,我大概的查了一下,好像用埃氏筛法的效率比较高。
以前我用Linux Shell也写过一个:

#!/system/bin/sh
max=1000
list="2"
rlist="2"
i=3
while [ $i -lt $max ]
do
[ "$(
echo "$list"|while read a
do
[ "$(($i%$a))" == "0" ]&&{
echo "1"
break 1
}
done
)" == "1" ]||c=$i

[ "$bj" == "" -a "$c" != "" ]&&{
[ "$((${c}*${c}))" -gt "$max" ]&&bj="1"
}

[ "$c" == "" ]||{
[ "$bj" == "1" ]||{
list="$list
$c"
}
echo "$c"
}
c=""
i="$(($i+1))"
done

不过效率极低……因为原生Shell是不支持数组之类的东西,所以其实并不能完全使用埃氏筛法……

使用Python做一个

当然Python还是可以用的,于是我理解了一下,做了一个出来:

maxprime=100000
rprimeset=set(range(2,maxprime+1))
lprimeset=set()
lastprime=0
while lastprime<=maxprime**0.5:
        lastprime=min(rprimeset)
        rprimeset=rprimeset-set(range(lastprime,maxprime+1,lastprime))
        lprimeset.add(lastprime)
primelist=sorted(list(rprimeset|lprimeset))
print(primelist)
#print(primelist,file=open(__file__[:__file__.rfind("/")]+"/prime.txt",'w+'))

这个效率确实比Shell做的好太多了,而且看起来也清晰易懂。在我的电脑上,1000000的质数只需要4s就能算出来

结局

不过我后来在某百科上查了一下他们用埃氏筛做的Python版本……然后我就酸了……他们的代码在我的电脑上只需要0.6s就能跑完1000000的质数……而且我估计他们的空间复杂度还比我小……

  #    python 原生实现
 
def primes(n):
    P = []
    f = []
    for i in range(n+1):
        if i > 2 and i%2 == 0:
            f.append(1)
        else:
            f.append(0)
    i = 3
    while i*i <= n:
        if f[i] == 0:
            j = i*i
            while j <= n:
                f[j] = 1
                j += i+i
        i += 2
 
    P.append(2)
    for x in range(3,n+1,2):
        if f[x] == 0:
            P.append(x)
 
    return P
 
n = 1000000
P = primes(n)
print(P)

感觉好难受,每次在网上搜的代码都比我写的好……算了,反正我也是在学习嘛。
后来我听说用欧拉筛法的效率更高……可惜我看完后不太理解……质数算法可真是复杂啊……

tags: Python - 质数 - 学习笔记
召唤伊斯特瓦尔