问题描述

π(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)