使用6k +/- 1規則提高試劃法素性測試

我正在審閱試劃法素性測試的基礎知識，並因此在代碼中實現它。使用6k +/- 1規則提高試劃法素性測試

1）運行試除法僅達平方根（N）

2）交易記憶時間通過創建一個篩高達正方形：可使用許多花樣等來增加該算法的性能根（n），然後在創建的篩上僅對質數中的試驗分區運行

但是，如果發現了n%6（n模6）的值，我無法找到將結果作爲複合返回的想法是1 or 5（使用6k +/- 1規則）。在我們的素數測定測試中使用這個規則是否會提高其性能？如果是，爲什麼在任何地方都沒有提到它？如果不是，爲什麼這樣呢？

感謝。

來源

2016-06-26 Tanmay Garg

對不起，不是一個答案，而是提示而不是使用週期性/循環篩？請參閱[Eratosthenes更快的順序比同時？]（http://stackoverflow.com/a/22477240/2521214） – Spektre

看來你屬於入門級的水平以上的類別（人誰永遠不會想出的想法）和低於人們尋找極致的性能。所以這個想法對初學者來說有點難以解釋，對於非常先進的人來說似乎是微不足道的。

它由三分之一減少了運行時間，或者讓你在同一時間測試更多的50％的數字。通過進行更少的除數不太大的測試，可以節省更多：假設您測試的數字大約爲十億。你有一個循環，除數d = 6k-1，你想測試d和d + 2 = 6k + 1。所以你只測試d^2≤p，你不測試（d + 2）^ 2≤p。最糟糕的情況是，你測試一個除數比你需要的多。最好的情況下，你可以節省數千次（d + 2）^ 2≤p的測試。

可以通過觀察到的唯一可能的素數≥30是保存稍微30K + 1，7，11，13，17，19，23，29，避免30K + 5和30K + 25

來源

2016-06-26 13:24:03 gnasher729

他的實際想法是首先測試'n％6'作爲初步過濾器，然後開始試用。這個想法不是很有幫助，但是這個答案顯示瞭如何修改它以提供幫助。 –

我喜歡你可以忽略'（d + 2）^ 2≤p'測試的部分，並導致另一個除數的最壞情況丟失。真的很體貼，謝謝！ –

您的測試n % 6的想法是完全等效於測試n % 2和n % 3 - 因此，如果你選擇後者作爲普通審判庭然後做前者是多餘的部分。

這確實還清

密切相關的想法是（考慮後2和3）僅看形式6k+1，6k-1試除數，如@ gnasher729在他們的出色答卷解釋。

來源

2016-06-26 13:27:05

這一招的工作方式：請M的一幫小的素數的乘積。然後，測試數N時，就可以立即說N是複合如果（N％M）爲0或具有共同的因子與M.

您使用6的2的產物和3.中可能的模數0,1,2,3,4,5，只有1和5不具有2或3的因子。

雖然6沒有什麼特別的特殊之處 - 你也可以用同樣的技巧任何模量，雖然你想使它成爲小質數的產物，以最大化複合模量的密度。

需要注意的是，使這一檢查（如咬人的指示）後，你只需要測試試除數不具有共同的因素與M.

來源

2016-06-26 13:27:09

這裏的一般方法被稱爲Wheel Factorization。最簡單的輪子是專門對待2個，之後只是測試奇數：2個輪子。接下來最簡單的是2,3輪，你在你的問題中提到。 @ gnasher729給出了2,3,5輪以上的數字。

可以通過交替地加入2和4，從開始產生用於2,3-輪的數字5.

僞代碼：

boolean isPrime(num) 

    // Deal with factor 2. 
    if (num MOD 2 = 0) then 
    return (num = 2) 
    endif 

    // Deal with factor 3.  
    if (num MOD 3 = 0) then 
    return (num = 3) 
    endif 

    // Factors >= 5. 
    limit <-- 1 + sqrt(num) 
    trialFactor <-- 5 
    step <-- 2 
    while (trialFactor < limit) do 
    if (num MOD trialFactor = 0) 
     // Number not prime 
     return false 
    endif 
    trialFactor <-- trialFactor + step 
    step <-- 6 - step 
    endwhile 

    // Number is prime here. 
    return true 

end

這使用較少的內存比篩上，但是非常大的素數太慢了。

來源

2016-06-26 14:41:31 rossum

使用6k +/- 1規則提高試劃法素性測試

回答

相關問題