Hann Yang 2022-06-21 20:28 采纳率: 100%
浏览 77
已结题

挑战求素数函数的速度!

自定义一个求素数的函数: prime(n) = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..... ,其中 n = 1,2,3,4,5,6,7,8,9,10......

时间限制:第10万项在9秒以内,第1万项在0.3秒以内(计时硬件:Pentium(R)Dual-Core E5400 + 4GB Ram)

>>> import time
>>> t=time.time();prime(100000);time.time()-t
1299709
8.907615661621094
>>> t=time.time();prime(10000);time.time()-t
104729
0.296400785446167
>>> [prime(i+1) for i in range(10)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
  • 写回答

3条回答 默认 最新

  • 天元浪子 Python领域优质创作者 2022-06-22 09:34
    关注
    import time
    import numpy as np
    
    def find_prime(top):
        """找出小于top的所有质数"""
        
        prime_list = list() # 空数组,用于存放找到的质素
        mid = int(np.sqrt(top)) # 判断100是否是质数,只需要分别用2,3...等质素去除100,看能否被整除,最多做到100的平方根就够了
        nums = np.arange(top) # 生成0到上限的数组,数组元素的值等于其索引号,相对于python的[0,1,2,3,...]
        nums[1] = 0 # 数组第1和元素置0,从2开始,都是非0的
        
        while True: # 循环
            primes = nums[nums>0] # 找出所有非0的元素
            if primes.any(): # 如果能找到
                p = primes[0] # 则第一个元素为质数
                prime_list.append(p) # 保存第一个元素到返回的数组
                nums[p::p] = 0 # 这个质数的所有倍数,都置为0(表示非质素)
                if p > mid: # 如果找到的质数大于上限的平方根
                    break # 则退出循环
            else:
                break # 全部0,也退出循环
        
        prime_list.extend(nums[nums>0].tolist()) # nums里面剩余的非0元素,都是质数,合并到返回的数组中
        return prime_list # 返回结果
    
    if __name__ == '__main__':
        
        for top in (10_000, 100_000, 1_000_000, 10_000_000):
            t0 = time.time()
            prime_list = find_prime(top)
            t1 = time.time()
            print('查找%d万以内的质数耗时%0.3f秒,共找到%d个质数'%(top//10000, t1-t0, len(prime_list)))
    

    运行结果:

    查找1万以内的质数耗时0.001秒,共找到1229个质数
    查找10万以内的质数耗时0.023秒,共找到9592个质数
    查找100万以内的质数耗时0.653秒,共找到78498个质数
    查找1000万以内的质数耗时14.954秒,共找到664579个质数
    

    img

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 6月30日
  • 已采纳回答 6月22日
  • 专家修改了标签 6月21日
  • 创建了问题 6月21日

悬赏问题

  • ¥15 小贝360-4 配二个 华772S 设置WⅰFi5G 连接
  • ¥15 vs2022的QT报错,好像是缺少winextras
  • ¥15 怎么看 cst中一个面的功率分布图
  • ¥15 c语言数据结构求9999
  • ¥15 Fiddler无法对部分小程序抓包
  • ¥60 Python代码 ip首部检验和计算代码 版本协议 首部长度 源地址 目的地址 存活时间
  • ¥18 微机原理汇编的综合实验
  • ¥15 LD衰减图用R语言对其可视化
  • ¥15 Mermaid语法生成的svg在Axure无法编辑
  • ¥15 Windchill二次开发