Python学习笔记 - 求质数 | Mayx的博客

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

# Python学习笔记 - 求质数

by mayx

这是一篇创建于 天前的文章，其中的信息可能已经有所发展或是发生改变。

AI摘要

这篇文章是作者在学习Python过程中，针对生成质数的任务分享了自己的实现方法，使用了埃氏筛法，但发现效率相比在学校资源中看到的原生Python埃氏筛和欧拉筛法实现低很多，他们的代码能在更短的时间内处理大量质数。作者虽然感到沮丧，但也意识到这是一个学习过程，且随后了解到欧拉筛法的原理较复杂。

- 起因
- 使用Python做一个
- 结局

讲真，我酸了……

#
起因

在学习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 - 质数 - 学习笔记 查看原始文件

#### 推荐文章

Loading...

上一篇：Python学习笔记 - Turtle
下一篇：Mayx应聘失败(Python版)
想问这篇文章
召唤伊斯特瓦尔