NTh平方免費半素數

我在找n（< = 2000000）square free semi prime。我有下面的代碼來做到這一點。NTh平方免費半素數

int k = 0; 
for(int i = 0; i <= 1000; i++) 
{ 
    for(int j = i +1 ; j <= 2500; j++) 
    { 
     semiprimes[k++] = (primes[i]*primes[j]); 
    } 
} 
sort(semiprimes,semiprimes+k);

primes[]是素數列表。

我的問題是，我得到了n = 2000000的不同值，對for循環有不同的限制。有人能說出一種方法來正確計算這些限制嗎？

在此先感謝..

來源

2012-05-03 frodo

提示：第n次semiprime必須大於n。如果'p'是小於'n/2'的最大素數，那麼'2p'是一個半數，應該包含在你的計數中。 –

@ Jeffrey Sax請你詳細說明一下嗎？我還沒有弄明白！繼續採取錯誤的限制。 – frodo

你要計算的第n個第一半素無平方數。 「第一個」意味着您必須在特定值下生成所有這些參數。您的方法包括生成大量這些數字，對它們進行排序並提取第n個第一個值。

這可能是一個很好的方法，但您必須擁有所有生成的數字。在嵌套循環中有兩個不同的限制是錯過其中一些的好方法（在你的例子中，你不計算primes[1001]*primes[1002]應該在semiprimes）。

爲避免此問題，您必須計算一個正方形中的所有半素數，例如[1,L]*[1,L]，其中L是兩個循環的限制。

要確定L，所有你需要的是它的數量。設N爲primes[L-1]*primes[L-1]下的半素數無平方數的數目。

N = (L * L - L)/2

L * L是成對的乘法的總數目。 L是平方的數量。這有兩個被兩除以得到正確的數字（因爲primes[i]*primes[j] = primes[j]*primes[i]）。

你想選擇L，使得n < = N。所以對於n = 2000000：

int L = 2001, k = 0; 
    for(int i = 0; i < L; i++) 
    { 
     for(int j = i+1 ; j < L; j++) 
     { 
      semiprimes[k++] = (primes[i]*primes[j]); 
     } 
    } 
    sort(semiprimes,semiprimes+k);

來源

2012-05-24 14:09:58 romain

L的這個值是錯誤的！見Jeffrey Sax上面的評論。你將會丟失類型爲2 * p的semiprimes，其中p是遠遠超過素數的素數[2000]。 –

我不相信一個方法，通過計算一個盒子內的所有semiprimes將在任何合理的時間內工作。假設我們繪製了前200萬次半素的因子（p，q）。爲使圖更對稱，讓我們爲（p，q）和（q，p）繪製一個點。該圖不形成一個很好的矩形區域，但看起來更像是雙曲線y = 1/x。這種雙曲線延伸得相當遠，並且遍及整個包含這些矩形的矩形將會浪費大量計算。

您可能需要考慮首先解決「N下有多少個半素數？」問題。然後使用二進制搜索。每個查詢可以在大約sqrt（N）步驟中完成（提示：二進制搜索罷工再次）。你需要一個相當大的素數表，至少可以達到100萬，可能更多。儘管這可以通過一些預先計算的任意大的常數因子來削減。

來源

2012-06-14 04:59:28

NTh平方免費半素數

回答

相關問題