減少時間篩法的複雜性發現的素數

請考慮下面的代碼減少時間篩法的複雜性發現的素數

public void printSievePrimes() 
     { 
      int[] temp = new int[count]; 
      for (int j = 2; j * j < temp.Length; j++) 
      { 
       for (int i = j * j; i < temp.Length; i += j) 
       { 
        primesFound[i] = false; 
       } 
      } 
      for (int i = 2; i < temp.Length; i++) 
      { 
       if (primesFound[i] != false) 
        Console.WriteLine("PrimeFound is:" + i); 
      } 

     }

上述方法被稱爲尋找primes.It是這樣的篩法;

1開始從圖2和抵消它隨後facotors像4,6,8 ...從3

2開始和抵消它隨後facotors像9,12,15 ...

3個4..is已經取消了

4從5開始... ...等等

我做了它，它正在well.but要減少它的複雜度爲O（n）或O（ nlogn）可以做些什麼？另一個問題是，我必須通過數組循環來獲得最大的素數是有辦法找到最有效的方式找到最大的素數？

來源

2014-02-14 Naseer Ahmed

剛剛計算Sum [j = 2 .. Sqrt（j）]（（N-j^2）/ j） –

其文獻中的順序爲O（nloglogn） –

這裏是walfram所說的：http：// www ？.wolframalpha.com /輸入/ I =總和+％28％28N + - + J％5E2％29％2Fj％29 +從+ J +％3D + 2 +到+ SQRT％28N％29 –

您發佈的算法具有複雜度O（N log（N））。你可以用這個變化雖然加快速度有點...我不知道這是否會提高算法的複雜度（可能會）

for (int j = 2; j * j < temp.Length; j++) 
{ 
    if (primesFound[j] == false) continue; 

    for (int i = j * j; i < temp.Length; i += j) 
    { 
     primesFound[i] = false; 
    } 
}

基本上...您發佈的代碼不會跳過號碼4，因爲它從不檢查數字是否已經被取消。

來源

2014-02-14 21:53:46 QuestionC

減少時間篩法的複雜性發現的素數

回答

相關問題