内存足够大,写程序输出2到2000的质数。
'''华为面试题目 求2到2000的质数''' N = 2000 number = list( range(2, N+1) ) times = 0 checknum = list(range(2,int((N+1)/2)+1)) for i in checknum: for index in number: times += 1 if index != i: if index/i == int(index/i): number.remove(index) if index in checknum: checknum.remove(index) print(number) print("尝试%d次"%times)
以上比较朴素、比较笨、比较快速的实现了一个程序。如果作为本科生,写出这样的程序或可以接受。
设计思想:
验证一个大于2的数是不是质数,当然只要从2循环到int(N/2),去除这个数,如果能够整除,被除数不等于除数,则这就是一个合数。如果都不能整除,则这是一个质数。
但是如果从2一直到N,都这样求一遍,时间复杂度太高了。比如,计算49是不是质数,前面会使用4和6去除,问题是4和6本身就是合数,其实应该使用质数去除49验证,也就是用2 3 5 7,但是,怎么直接拿这种质数去除呢?那么以上程序的朴素思想1就来了:维护两个表,一个表number是从2到N,一个表checknum是从2到N/2,checknum专门存储除数。每一次取除数都从checknum取,一旦checknum能够整除number,判断出这个number是一个合数,就把它从两个表里面删去。由于我们使用的是python的for in 形式的循环,动态修改循环列表,可以保证目前用于检查的数是个质数,不会从未来的表里删掉。比如我们验证4/2,则4应该从checknum表里面删掉;而不会因为验证一个m,导致了小于m的数从number被删掉,这样的话,不会需要回溯数组。于是就有了以上程序。
当然这个程序并不是某一种最优解,需要考虑优化解法。
有一种获取一个范围内的质数的方案叫“筛法”,就是把这个范围内的数都写出来,用最小的质数2来除,除尽就划掉。再用下一个质数3来除,除尽就划掉。那么利用这种思想,我们可以有第2种程序:
从list里面取除数,从2开始,一个个循环去除list包含的元素,查找list中的合数,找到合数就从list删掉(当然你要考虑到,list的查找+删除remove函数由于做了大量的数据位移,实际是很耗时的),然后,list的下一个数:3。当3筛过之后,由于4已经在除以2的一轮中删掉了,所以下一个除数是5。这就避免了使用合数来除list中的数。
另外,用2到N/2中所有的质数来除吗?也不是。显然,实际应该从2到int(sqrt(N))来除。比如,N=100,由于除以7的时候,7*14=98已经被删除,在这之前的7*11=77也被删除了,已经不需要使用int(sqrt(100))+1=11除了,11*8 11*9 都在更早被删除,所以只要小于等于10,就可以了。为什么要等于?比如N=121,int(sqrt(N))=11,需要除到11时才能把121去掉。
那么我们就有了下面的解法:
'''华为面试题目 求2到2000的质数''' import math N = 2000 number = list( range(2, N+1) ) times = 0 index = 0 #index表示现在的除数是list里的第几个数 #flag定为N的算术平方根 flag = int(math.sqrt(N)) for i in number: x = number[index] #x 从number中取数,如果大于flag本轮循环结束 if x > flag:break #从index+1开始向后遍历,如果能够整除则从number删除 for bei in number[index+1:]: times += 1 if bei/x == int(bei/x): number.remove(bei) index += 1 #最终剩下的就是质数 print(number) print("尝试%d次"%times)
这个解法还有没有改进空间呢?还是有的。在for bei in number[index+1:]这里,这是做了一个列表的切片。每做一个切片就是复制数组的一段,还是有比较大的开销。那么,我们如果把这个循环换成:自index+1到len(number)循环,取number变量的事情放在里面,则会省去一些数组复制的空间开销。
但是,一旦这样处理,删除、取变量都是同一个数组操作,要注意控制里面的循环变量。