Board logo

标题: [原创代码] python吹蜡烛 [打印本页]
作者: happy886rr    时间: 2016-4-13 18:20     标题: python吹蜡烛

本帖最后由 happy886rr 于 2016-4-14 23:09 编辑

　　素数（prime number）又称质数。就是除了1和它本身之外不能被其它任何数整除，最小的素数是2。如果让你打印出100万以内的所有素数，你该怎么做。大家都喜欢逐一判断1到1000000的每一个奇数是否是素数，那么就可以只需for循环50万次。

　　但是这都不够效率,有没有连除法都不用的。好吧，奇特的处理方法(亦可移植到批处理上)，如过把１到100万的数都表示出来，需要花费上万行txt才能装得下。但我们可以构造一个数组r=[1111111111111...]，r就是有100万个1的字符串，你也可以把每一个1都当做一个蜡烛，每个蜡烛的位置就可以表示一个数，第2个位置表示2，第10万个位置代表10万。然后我们先把2的倍数，也就是4、6、8、10...位置上的蜡烛“1”吹灭（就是赋值为0），这样r就变为[10101010......];好了第一轮已经完毕，开始第二轮，把3的倍数，也就是6、9、12、15...位置上的蜡烛“1”吹灭（赋值为0），这时r就变为[100010100010...],一看就是100010的不断循环。这还没完，继续第4、5、6轮一直到第根号100万。

　　我想你已经看出端倪来了，它只要判断到第(根号100万)个数就可以收工回家了（因为后边剩的没吹灭的蜡烛＂1＂的位置都是素数不必判断），根号100万是1000，for这么少就完事了，这不是要逆天了吗？还有更逆天的，既然第二轮吹完蜡烛后，数组r已经变为100010的不断循环，那我们可以直接就让r=100010的循环，就省了两轮，那能省N轮吗？自己看吧，跟自助一样，能干掉几轮就干几轮，不勉强。我就干两轮于是就有了如下的python代码:
  1. # Python 吹蜡烛

  2. N=1000000

  3. r=[1,0,0,0,1,0]*(N//6+1)

  4. r.insert(0,"0");r[3]=1

  5. for i in range(5,int(N**0.5)+1,2):

  6. 	if r[i]==0:

  7. 		continue

  8. 	for j in range(i*i,N+1,2*i):

  9. 		r[j]=0

  10. for i in range(1,N+1):

  11. 	if r[i]==1:

  12. 		print(i,",",end="")
复制代码
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
　　问题解决的省时又省力，再干一道题。话说欧拉计划的题目越往后难度成几何倍数增长，试了一下，果真不假。就拿第501题来说：

《八个约数》
　　24的八个约数是1、2、3、4、6、8、12和24。在不超过100的数中有十个数恰好有八个约数，分别是24、30、40、42、54、56、66、70、78和88。在不超过n的数中，记f(n)个数恰好有八个约数。已知f(100) = 10，f(1000) = 180以及f(10^6) = 224427。求f(10^12)。

　　首先应该搞清楚这是在考什么，考的是约数吗？当然不是。什么样的数会有８个约数，首先引入个概念，那就是任何自然都可以写成Ｎ＝(p1^k1)*(p2^k2)*(p3^k3)***  注：p1、p2...均为素数。
显而易见N的约数有多少？不就是(k1+1)*(k2+1)*(k3+1)***吗！（就是小学的乘法原理）。那好让这个(k1+1)*(k2+1)*(k3+1)***=8，由于8=2*2*2=1*7=2*4，因此你可以推出有8个约数的数必可以表示为
形如：p1*p2*p3或者(p1^7)或者p1*(p2^3)这三种形式,注：p1、p2...均为素数。

　　闹了半天是看每个数能否表示为三个素数连乘积、或一个素数的7次方，或一个素数乘以另一个素数的3次方，如果能则此数必有8个约数。我想还是分类谈论吧：
　　首先、先统计10的12次方内，所有能表示为一个素数的7次方的数，这些数都满足8约数。也就是p1^7<10^12,推出满足条件的p1为2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 共15个
　　再次、统计10的12次方内，所有能表示为一个素数乘以另一个素数的3次方和三个素数连乘积的数，也是就是找形如p1*(p2^3)和p1*p2*p3的数，这里我们就需要知道10的12次方内到底有多少个素数了，然后利用排列组合算出它的数目，再去除相交的集合。计算有多少个素数，那用吹蜡烛吧，但是你会发现10的12次方好大一个数啊，python的数组长度只支持到1亿就溢出了，循环了好几圈都没反应。所以说python也有不能做到的事，它判断一个素数就要for好多下，再说欧拉计划的最后几题，根本不是能秒出答案的，都是算法压轴题，算了，我也不想浪费时间了，直接上mathematica，强大的科学计算软件，自带判断素数和个数的函数，不想for了，直接套了最好的素数pi估值公式，在容斥原理的帮助下，经过35分钟得到了答案 197912312715。　
作者: codegay    时间: 2016-4-13 18:51

python的is 是判断对像的地址是不是一样。
应该用==
作者: happy886rr    时间: 2016-4-13 18:58

回复 2# codegay
语法不是太懂，我语法很poor，现在python只会用for.计算全靠for。



欢迎光临 批处理之家 (http://www.bathome.net/) Powered by Discuz! 7.2