π(x) = 素數≤x的數量
下面的代碼給出了小于或等于N的素數
對于N<=100000，它的作業原理是完美的。輸入-輸出表
|輸入|輸出| |-------------|---------------| | 10 | 4? ! | 100 | 25? | 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__"/span>: N = int(input() start = time.time() print(len(pi(N)) end= time.time() print(end-start)
uj5u.com熱心網友回復：
你可以從這個執行緒中以最快的方式閱讀，就像下面這樣，用這個函式對n = 1000000，我正確地找到78498質數。（我在這個函式中改了一行）
從：
return（[2] [i for i in range(3, n,2) if sieve[i]] )
要：
return len([2] [i for i in range（3, n,2) if sieve[i]] )
最后：
def primes（n）。
sieve = [True] * n
for i in range(3,int(n**0。 5) 1,2）。)
if sieve[i]:
sieve[i*i:: 2*i]=[False]*((n-i*i-1)//(2*i) 1)
return len([2] [i for i in range(3, n,2) if sieve[i]】)
inp = [10, 100, 1000, 10000, 100000, 1000000[/span>]
for i in inp:
print(f'{i}:{primes(i)}'/span>)
輸出：
10: 4
100:25。
1000: 168
10000:1229。
100000:9592。
1000000:78498。
uj5u.com熱心網友回復：
只有當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)/span>
prm_lst = set([] )
while nums:
p = nums.pop()
prm_lst.add(p)
nums.difference_update(set(range(p, x 1, p))
# print(prm_lst)/span>
return prm_lst
if __name__ == "__main__"/span>:
N = int(input()
start = time.time()
print(len(pi(N))
end = time.time()
print(end - start)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/325742.html
標籤：