华为编程面试题目 求2到2000的质数 源程序筛法求质数

简介: 华为编程面试题目 求2到2000的质数 源程序筛法求质数

内存足够大,写程序输出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变量的事情放在里面,则会省去一些数组复制的空间开销。


但是,一旦这样处理,删除、取变量都是同一个数组操作,要注意控制里面的循环变量。



目录
相关文章
|
4月前
|
Java 开发者
Java面试题:请解释内存泄漏的原因,并说明如何使用Thread类和ExecutorService实现多线程编程,请解释CountDownLatch和CyclicBarrier在并发编程中的用途和区别
Java面试题:请解释内存泄漏的原因,并说明如何使用Thread类和ExecutorService实现多线程编程,请解释CountDownLatch和CyclicBarrier在并发编程中的用途和区别
56 0
|
4月前
|
存储 缓存 监控
Java面试题:在Java中,对象何时可以被垃圾回收?编程中,如何更好地做好垃圾回收处理?
Java面试题:在Java中,对象何时可以被垃圾回收?编程中,如何更好地做好垃圾回收处理?
68 0
|
5月前
|
算法 Java 调度
《面试专题-----经典高频面试题收集四》解锁 Java 面试的关键:深度解析并发编程进阶篇高频经典面试题(第四篇)
《面试专题-----经典高频面试题收集四》解锁 Java 面试的关键:深度解析并发编程进阶篇高频经典面试题(第四篇)
72 0
|
1月前
|
缓存 关系型数据库 MySQL
面试题目总结
面试题目总结
71 6
|
1月前
|
Java C++ Python
【面试宝典】深入Python高级:直戳痛点的题目演示(下)
【面试宝典】深入Python高级:直戳痛点的题目演示(下)
|
1月前
|
设计模式 Unix Python
【面试宝典】深入Python高级:直戳痛点的题目演示(上)
【面试宝典】深入Python高级:直戳痛点的题目演示(上)
|
3月前
|
Java
【Java基础面试三十五】、谈谈你对面向接口编程的理解
这篇文章讨论了面向接口编程的概念,强调接口作为一种规范和实现分离的设计哲学,可以降低程序模块间的耦合度,提高系统的可扩展性和可维护性。
|
3月前
|
人工智能 大数据 云计算
开启第二增长曲线!副业必备6000+课程、免费算力、编程实践助你飞速成长!
阿里云为高校学生提供全方位学习计划,含6000+免费精品课程与自测题,及免费在线编程练习。学生可免费获2.68亿小时算力,包括云服务器ECS、对象存储OSS等资源。同时,参与阿里云天池竞赛赢取高额奖金,并通过训练营获得实践经验和证书。借助这些资源,学生能紧跟信息化与AI潮流,为职业发展奠定坚实基础。
99 2
|
5月前
|
缓存 Java 数据库连接
java面试题目 强引用、软引用、弱引用、幻象引用有什么区别?具体使用场景是什么?
【6月更文挑战第28天】在 Java 中,理解和正确使用各种引用类型(强引用、软引用、弱引用、幻象引用)对有效的内存管理和垃圾回收至关重要。下面我们详细解读这些引用类型的区别及其具体使用场景。
79 3
|
4月前
|
设计模式 安全 Java
Java面试题:请列举三种常用的设计模式,并分别给出在Java中的应用场景?请分析Java内存管理中的主要问题,并提出相应的优化策略?请简述Java多线程编程中的常见问题,并给出解决方案
Java面试题:请列举三种常用的设计模式,并分别给出在Java中的应用场景?请分析Java内存管理中的主要问题,并提出相应的优化策略?请简述Java多线程编程中的常见问题,并给出解决方案
108 0