優化素數函數速度

Question

我正在寫一個函數來列出在特定起始值'N以上的素數'M'數。在這一點上，我只想盡可能地提高功能（即：FAST！）。我真的沒有想法，所以任何幫助將不勝感激。代碼（matlab）如下：

function PrimeNumbersList = primes_after(N,M) 
tic; 
x = N; 
s = 1; 
PrimeNumbersList = 0; 
if mod(N,2) == 0 
while numel(PrimeNumbersList) < M 

if isprime(x) == 1 
    PrimeNumbersList(s) = x; 
    x=x+2; 
    s=s+1; 
else 
    x=x+2; 
end 
end 
else 
while numel(PrimeNumbersList) < M 

if isprime(x) == 1 
    PrimeNumbersList(s) = x; 
    x=x+1; 
    s=s+1; 
else 
    x=x+1; 
end 
end 
end 
tElapsed=toc 
end 

Answer 1

你可以做的一件事是隻考慮奇數（增加2而不是1）。這會將循環迭代次數減半。

isprime可能會有收益，取決於它的實施方式。這一切都取決於你需要的準確度（即卡邁克爾號碼是否允許？）。

編輯：

你所做的修改並沒有真正解決任何事情。試試這個：

function PrimeNumbersList = primes_after(N,M) 
    tic; 
    x = N; 
    s = 1; 
    PrimeNumbersList = 0; 

    if mod(x,2) == 0 
     if x == 2 
      PrimeNumbersList(s) = x; 
      s=s+1; 
     end 
     x=x+1; 
    end 

    while numel(PrimeNumbersList) < M 
     if isprime(x) == 1 
      PrimeNumbersList(s) = x; 
      s=s+1; 
     end 
     x=x+2; 
    end 

    tElapsed=toc 
end 

另外，你或許可以改變numel(PrimeNumberList) < M到s < m，避免函數調用。小的優化，但是，嘿，我們已經分裂頭髮。

編輯：

如果你不能接受的錯誤（例如卡邁克爾數），那麼你堅持執行緩慢的isprime（asuming它是正確的）。這是因爲檢查數字是否是素數是困難的。 Fermat s Little Theorem is a clever shortcut, but isprime`無論如何都可以使用額外的驗證來消除錯誤。

你真的沒有什麼可以做的。如果你願意用不同的語言重寫這個，那麼我推薦Haskell;它爲生成數字提供了很好的支持，並將您的代碼轉換爲大約3行的函數（大概是這樣）。

我不知道MATLAB不夠好，以消除一些額外的週期，但這裏有一些建議：

• 如果MATLAB可以追加到PrimeNumbersList，做到這一點，而不是設置索引。這可能會更快（這是在Javascript）
  • 這將擺脫s變量，從而消除了另外的
• 使用s代替numel（嘗試，取代上述嘗試這個）

Answer 2

這裏有一些潛在的速度增加。

function PrimeNumbersList = primes_after(N,M) 
tic; 

x = 0; 
if (N mod 2) == 0 && N != 2 
    x = N + 1; 
else 
    x = N; 
end 

s = 1; 
PrimeNumbersList = 0; 
tempInt = x - 1; 
isPrime = 1; 

while numel(PrimeNumbersList) < M 

    while tempInt > 1 && isPrime 
     if (x mod tempInt) == 0 
      isPrime = 0; 
     end 
     tempInt=tempInt-1; 
    end 

    if isPrime 
     PrimeNumbersList(s) = x; 
     x=x+1; 
     s=s+1; 
    else 
     x=x+1; 
    end 

end 
tElapsed=toc 
end 

好了，現在的解釋：

首先，我檢查，看看是否N是偶數。如果是這樣，我增加1只是爲了確保它是奇怪的（雖然不一定是總理）。因爲它是素數，但是可以被2整除。

由於我不知道isPrime（）的速度，我只寫了我自己的（基於一個簡單的質數證明號）。隨意檢查你的tic/toc。

除此之外，我看不到更多的速度增加。我的2美分。

Answer 3

做不是迭代通過一組數字測試每個素數。這將是不可能的緩慢。您正在尋找的算法被稱爲Eratosthenes的分割篩。

雖然Eratosthenes的篩網速度非常快，但它需要O（n）空間。對於篩選素數，可以通過在連續的片段中執行篩分將其減少到O（sqrt（n））加上O（1）的比特數。在第一個分段中，計算分段內每個篩分質數的最小倍數，然後以正常方式標記複合質量的多個篩分質數;當使用所有篩分質數時，該分段中剩餘的未標記數字是質數。然後，對於下一個分段，每個篩分質數的最小倍數是在前一個分段中結束篩分的倍數，因此篩分繼續直到完成。

考慮從20到200的分段篩選100到200的例子; 5個篩選素數是3,5,7,11和13.在100到120的第一段中，比特數有10個時隙，其中時隙0對應於101，時隙k對應於100 + 2k-1，時隙9對應於119.分段中的3的最小倍數是105，對應於時隙2;時隙2 + 3 = 5和5 + 3 = 8也是3的倍數。時隙2處的5的最小倍數是105，時隙2 + 5 = 7也是5的倍數.7的最小倍數是105在時隙2處，時隙2 + 7 = 9也是7的倍數。依此類推。

函數素數需要參數lo，hi和delta; lo和hi必須是偶數，並且lo必須大於天花板（sqrt（hi））。段的大小是兩倍三角洲。長度爲m的數組ps包含小於sqrt（hi）的篩選素數，刪除2，因爲偶數會被忽略，並且數組qs包含到相應篩選素數當前片段中最小倍數的篩子位陣列的偏移量。每個段之後，LO通過兩次增量前進，所以對應於篩bitarray的索引j的數目爲LO + 2J + 1

function primes(lo, hi, delta) 
    sieve := makeArray(0..delta-1) # bitarray 
    # calculate m and ps as described in text 
    qs := makeArray(0..m-1) # least multiples 
    for i from 0 to m-1 
    qs[i] := (-1/2 * (lo + ps[i] + 1)) % ps[i] 
    while lo < hi 
    for i from 0 to delta-1 
     sieve[i] := True 
    for i from 0 to m-1 
     for j from qs[i] to delta step ps[i] 
     sieve[j] := False 
     qs[i] := (qs[i] - delta) % ps[i] 
    for i from 0 to delta-1 
     t := lo + 2*j + 1 
     if sieve[i] and t < hi 
     output t 
    lo := lo + 2*delta 

對於上面給出的樣品，這被稱爲質數（100， 200，10）。在上面給出的例子中，qs最初是[2,2,2,10,8]，對應於最小倍數105,105,105,121和117，並且針對第二段重置爲[1,2,6， 0,11]，對應於最小倍數123,125,133,121和143。該算法非常快;你應該能夠在不到一秒的時間內生成幾百萬個素數。

如果您想了解更多關於使用素數編程的信息，我會在我的博客上謙虛地推薦this essay。