我制作了一個程式來查找低于給定數字的素數。
number = int(input("Enter number: "))
prime_numbers = [2] # First prime is needed.
for number_to_be_checked in range(3, number 1):
square_root = number_to_be_checked ** 0.5
for checker in prime_numbers: # Checker will become
# every prime number below the 'number_to_be_checked'
# variable because we are adding all the prime numbers
# in the 'prime_numbers' list.
if checker > square_root:
prime_numbers.append(number_to_be_checked)
break
elif number_to_be_checked % checker == 0:
break
print(prime_numbers)
該程式檢查低于作為輸入給出的數字的每個數字。但質數只是形式6k ± 1。因此，我沒有檢查所有數字，而是定義了一個生成器，它生成6k ± 1低于輸入給定數字形式的所有數字。（我在prime_numbers串列中也添加了 3 ，同時將其初始化為2,3不能是 form 6k ± 1）
def potential_primes(number: int) -> int:
"""Generate the numbers potential to be prime"""
# Prime numbers are always of the form 6k ± 1.
number_for_function = number // 6
for k in range(1, number_for_function 1):
yield 6*k - 1
yield 6*k 1
顯然，該程式應該快得多，因為我檢查的數字相對較少。但是，與直覺相反，該程式比以前慢了。這背后的原因可能是什么？
uj5u.com熱心網友回復：
在每六個數字中，三個是偶數，一個是 3 的倍數。另外兩個是 6-互質數，因此可能是質數：
6k 0 6k 1 6k 2 6k 3 6k 4 6k 5
even even even
3x 3x
對于三個偶數，您的素數檢查僅使用一個除法（乘以 2），而對于第 4 個數字，則使用兩個除法。總之，您要避免五個分裂。
但是每次呼叫生成器也有其成本。如果您只是將呼叫替換range為創建生成器的呼叫，但將其他代碼保留原樣 (*)，則您沒有充分發揮節約潛力。
為什么？因為 (*) 如果是這樣的話，雖然你現在確實只測驗了 1/3 的數字，但你仍然用 2 和 3 來測驗它們中的每一個。不必要的。而且顯然發電機的使用成本太高了。
這種稱為輪因式分解的技術的要點是不通過構造來測驗已知不是它們的約數的素數的 6-互素數（在這種情況下） 。
因此，您必須從 eg 開始，并在您的可除性測驗回圈中prime_numbers = [5,7]使用它，而不是所有以 2 和 3 開頭的素數，這是您不需要的。
uj5u.com熱心網友回復：
將嵌套 for 回圈與平方根一起使用會導致計算量很大，而是查看 Prime Sieve Algorithm，它的速度要快得多，但確實會占用一些記憶體。
uj5u.com熱心網友回復：
使用 6n±1 想法的一種方法是通過步進 2 然后步進 4 在主回圈中交替步長。我的 Python 不好，所以這是偽代碼：
function listPrimes(n)
// Deal with low numbers.
if (n < 2) return []
if (n = 2) return [2]
if (n = 3) return [2, 3]
// Main loop
primeList ← [2, 3]
limit ← 1 sqrt(n) // Calculate square root once.
index ← 5 // We have checked 2 and 3 already.
step ← 2 // Starting step value: 5 2 = 7.
while (index <= limit) {
if (isPrime(index)) {
primeList.add(index)
}
index ← index step
step ← 6 - step // Alternate steps of 2 and 4
}
return primeList
end function
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/537625.html
下一篇：鏈表c 中的append方法