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万次。

  但是这都不够效率,有没有连除法都不用的。好吧,奇特的处理方法(亦可移植到批处理上),如过把1到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)。

  首先应该搞清楚这是在考什么,考的是约数吗?当然不是。什么样的数会有8个约数,首先引入个概念,那就是任何自然都可以写成N=(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