# π(X)=素数≤x

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))
#print(nums)
prm_lst = set([])
while nums:
p = nums.pop()
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)
``````

### 推荐答案

``````import time

import sortedcontainers
from operator import neg

def pi(x):
nums = sortedcontainers.SortedSet(range(3, x + 1, 2), neg)
# print(nums)
prm_lst = set([])
while nums:
p = nums.pop()
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)
``````