[原创代码] python分片应用~秒出一亿内素数

happy886rr

　　在python中分片的扩展形式：str[I,J,K]意思是从I到J-1，每隔K个元素索引一次，如果K为负数，就是按从右往左索引。那么这个分片到底有什么作用呢？承接上一集“吹蜡烛”里的“打印出100万以内的所有素数“。

　　当时使用的是for循环去吹蜡烛，外层for生成素数，内层for吹烛，感觉for循环嵌套的效率非常低，发现吹蜡烛这个事用分片就可以做，没必要使用for。于是，全部替换成分片操作，效率瞬间提升10倍。但是每个蜡烛如果都用普通数组表示也忒非内存了！无意中发现python教程中还有bytearray这种字节型数组，好家伙这不是要逆天了吗？一个字节8位，为了少写点代码，就不研究怎么用bit来表示蜡烛了，直接用了byte表示蜡烛，效率再次提升3倍，最后利用素数循环节（直接跳过前４轮）再提速0.4秒。实现0.8秒左右便可构建出一亿内的素数（当然不算打印时间），只比julia慢0.2秒。

#---------------------Python Primes---------------------
def primes(N):
	print("构建{0}内的素数...".format(N))
	L=[0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1]
	r=bytearray(L)*(N//210)+bytearray(L[0:N%210])
	r[1]=0;r[2]=r[3]=r[5]=r[7]=1
	for i in range(11,int(N**0.5),2):
		if r[i]:r[i*i::i*2]=bytearray([0])*((N-i*i)//(i*2)+1)
	input("是否开始打印？（回车）")
	for i,p in enumerate(r):
		if p:
			print(i,",",end="")
#-------------------------------------------------------
primes(10**8)COPY

　　后来又想，吹蜡烛太费气力了，如果要打印出一亿以内的所有素数，那么我要吹灭数千万根蜡烛，还不如改吹蜡烛为点蜡烛，这个算法没有办法用分片实现，用Ｃ语言试了下，效率很满意，0.130秒出一亿内素数。可能由于python是脚本语言，同样的算法速度总是无法跟C比。

　　以下是模块化后的版本，筛选一亿内素数速度接近0.6秒。

#---------------------Count Time------------------------
def Tim(X):
	import time
	def F(*a, **b):
		t=time.time()
		a=X(*a, **b)
		print("[{0}s @{1}]".format(time.time() - t, X.__name__))
		return a
	return F
#---------------------Primes----------------------------
@Tim
def primes(N):
	print("构建{0}内的素数...".format(N))
	r=bytearray([1])*(N//2)
	for i in range(3,int(N**0.5)+1,2):
		if r[i//2]:r[i*i//2::i]=bytearray((N-i*i-1)//(i*2)+1)
	return r
#---------------------Print Primes----------------------
def printf(R):
	input("开始打印？（回车）")
	R[0]=0;print(2,",",end="")
	for i,p in enumerate(R):
		if p:
			print(i*2+1,",",end="")
#---------------------Main------------------------------
 
R=primes(10**8)
printf(R)COPY

　　将分片函数改造一下，变成身为Primest(K)函数，返回第K个素数。高性能的分片函数筛选器，寻找第K个素数，只需筛选K*24范围内的数。

#---------------------Count Time------------------------
def Tim(X):
	import time
	def F(*a, **b):
		t=time.time()
		a=X(*a, **b)
		print("[{0}s @{1}]".format(time.time()-t, X.__name__))
		return a
	return F
#---------------------Primest---------------------------
@Tim
def Primest(K):
	N=K*24
	r=bytearray([1])*(N//3);r[0]=0;j=2
	for i in range(int(N**0.5)//3+1):
		if r[i]:
			I=3*i+1|1
			r[((I*I)//3)::2*I]=bytearray([0])*((N//6-(I*I)//6-1)//I+1)
			r[(I*I+4*I-2*I*(i&1))//3::2*I]=bytearray([0])*((N//6-(I*I+4*I-2*I*(i&1))//6-1)//I+1)
	for i,p in enumerate(r):
		if p:
			j+=1
			if j==K:
				print("* The {0}st prime number is ：{1}".format(K,i*3+1|1))
				break
#-------------------------------------------------------
 
Primest(10001)      #调用Primest(K)函数，返回第K个素数COPY

　　如此解欧拉计划第七题：求第一万零一个素数？可直接调用Primest(K)函数，0.001秒出答案。

codegay

可以括号把list写成几行.

	L=([0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,
	1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,
	0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,
	1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,
	1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,
	0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1])COPY

happy886rr

回复 2# codegay
codegay兄的技巧不错，但是我发现py不能存为ansi编码，每次都得另存utf8,。

523066680

回复 3# happy886rr

      因为你里面写了中文嘛

查了一下，要保存为gbk文本而不提示"Non-ASCII character"的话，在行首加入
#coding:gbk
或者
#encoding:gbk

参考链接
Python的中文问题解决办法

happy886rr

回复 4# 523066680
谢谢。你的bat显示技巧很赞，还有那些游动粒子，虽然bat只提供了echoset/p=。

ivor

主要是Python的 for 遍历循环拖累了速度

codegay

回复 3# happy886rr

那个不叫我的技巧。。。教程里可能也是有说到的，大约是我忘记了。我是在欧拉论坛里看别人的代码学会的。....

这个问题底下：https://segmentfault.com/q/1010000004929185

有人给出了Awesome Python Books 的链接： https://github.com/Junnplus/awes ... ter/README-ZH_CN.md


顺便也推荐给你。

codegay

编码问题，因为我是用IDLE或者sublime的，空文件好像都会被存成UTF8。
所以没有这个问题了。

happy886rr

回复 8# codegay
codegay兄给的链接很详细，写python非常有趣，像是搭积木。

codegay

我去，你这进步好快，装饰器都会用了。

happy886rr

回复 10# codegay
统计时间是必须的，但是没julia的@time好用。

codegay

回复 11# happy886rr


    你可以搜索一下python time()  和clock()的区别。
我印象里看的一些文章是推荐用clock()

523066680

回复 5# happy886rr


     我现在肠子都悔青了，没有趁早换C艹

bailong360

WOW,多发点,多发点
等俺去学Python时这些代码可都是宝贵的资料啊

codegay

回复 13# 523066680


    不晚不晚。

不如投奔我大julia阵营？