小于或等于x的素数 [英] Number of primes less than or equal to x

查看:68
本文介绍了小于或等于x的素数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

π(X)=素数≤x

下面的代码给出了小于或等于N的素数

N<;=100000,

  • 投入产出表

    |    Input    |   Output      | 
    |-------------|---------------|
    | 10          |     4✔       |
    | 100         |     25✔      |
    | 1000        |     168✔     |
    | 10000       |     1229✔    |
    | 100000      |     9592✔    |
    | 1000000     |     78521✘   | 
    

    但是,π(1000000)=78498

    import time
    def pi(x):
        nums = set(range(3,x+1,2))
        nums.add(2)
        #print(nums)
        prm_lst = set([])
        while nums:
            p = nums.pop()
            prm_lst.add(p)
            nums.difference_update(set(range(p, x+1, p)))
            #print(prm_lst)
        return prm_lst
    
    
    if __name__ == "__main__":
        N = int(input())
        start = time.time()
        print(len(pi(N)))
        end= time.time()
        print(end-start)
    

推荐答案

只有当nums.pop()返回质数时,代码才正确,而反过来,只有当nums.pop()返回集合中最小的元素时,代码才正确。据我所知,这不能保证是真的。有一个名为sortedcontainers的第三方模块,它提供了一个SortedSet类,可用于使您的代码只需很少的更改即可工作。

import time

import sortedcontainers
from operator import neg


def pi(x):
    nums = sortedcontainers.SortedSet(range(3, x + 1, 2), neg)
    nums.add(2)
    # print(nums)
    prm_lst = set([])
    while nums:
        p = nums.pop()
        prm_lst.add(p)
        nums.difference_update(set(range(p, x + 1, p)))
    # print(prm_lst)
    return prm_lst


if __name__ == "__main__":
    N = int(input())
    start = time.time()
    print(len(pi(N)))
    end = time.time()
    print(end - start)

这篇关于小于或等于x的素数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆