Eratosthenes的我的篩子花費太長時間

Question

我實施了Sieve of Eratosthenes來解決SPOJ問題PRIME1。雖然輸出結果很好，但我的提交超過了時間限制。我怎樣才能縮短運行時間？

int main() 
{ 
    vector<int> prime_list; 
    prime_list.push_back(2); 
    vector<int>::iterator c; 
    bool flag=true; 
    unsigned int m,n; 
    for(int i=3; i<=32000;i+=2) 
    { 
    flag=true; 
    float s = sqrt(static_cast<float>(i)); 
    for(c=prime_list.begin();c<=prime_list.end();c++) 
    { 
     if(*c>s) 
      break; 
     if(i%(*c)==0) 
     { 
      flag=false; 
      break; 
     } 
    } 
    if(flag==true) 
    { 
     prime_list.push_back(i); 
    } 
    } 
    int t; 
    cin>>t; 
    for (int times = 0; times < t; times++) 
    { 
    cin>> m >> n; 
    if (t) cout << endl; 
    if (m < 2) 
     m=2; 
    unsigned int j; 
    vector<unsigned int> req_list; 
    for(j=m;j<=n;j++) 
    { 
     req_list.push_back(j); 
    } 
    vector<unsigned int>::iterator k; 
    flag=true; 
    int p=0; 
    for(j=m;j<=n;j++) 
    { 
     flag=true; 
     float s = sqrt(static_cast<float>(j)); 
     for(c=prime_list.begin();c<=prime_list.end();c++) 
     { 
      if((*c)!=j) 
      { 
       if((*c)>s) 
        break; 
       if(j%(*c)==0) 
       { 
        flag=false; 
        break; 
       } 
      } 
     } 
     if(flag==false) 
     { 
      req_list.erase (req_list.begin()+p); 
      p--; 
     } 
     p++; 
    } 
    for(k=req_list.begin();k<req_list.end();k++) 
    { 
     cout<<*k; 
     cout<<endl; 
    } 
    } 
} 

Answer 1

剖析你的代碼，找到熱點，消除它們。 Windows，Linux分析器鏈接。

Answer 2

我認爲一種稍微加快篩選速度的方法是防止在這一行中使用mod運算符。

if(i%(*c)==0)

相反的（相對）昂貴的MOD操作的，也許如果你與你的除了反覆篩向前。

老實說，我不知道這是否正確。你的代碼很難閱讀，沒有評論和單字母變量名稱。

Answer 3

我會拋棄你所擁有的東西，並從一個真正的簡單的開始，只有在真正需要時纔會增加更多的複雜性。這裏是一個可能的起點：

#include <vector> 
#include <iostream> 

int main() { 
    int number = 32000; 
    std::vector<bool> sieve(number,false); 
    sieve[0] = true; // Not used for now, 
    sieve[1] = true; // but you'll probably need these later. 

    for(int i = 2; i<number; i++) { 
     if(!sieve[i]) { 
      std::cout << "\t" << i; 
      for (int temp = 2*i; temp<number; temp += i) 
       sieve[temp] = true; 
     } 
    } 
    return 0; 
} 

對於給定的範圍（高達32000），這個運行在遠低於第二（與定向到一個文件輸出 - 在屏幕上，它會通常會比較慢）。這取決於你從那裏...

Answer 4

你的代碼很慢，因爲你沒有實現Eratosthenes算法篩。該算法的工作原理如下：

1) Create an array with size n-1, representing the numbers 2 to n, filling it with boolean values true (true means that the number is prime; do not forget we start counting from number 2 i.e. array[0] is the number 2) 
2) Initialize array[0] = false. 
3) Current_number = 2; 
3) Iterate through the array by increasing the index by Current_number. 
4) Search for the first number (except index 0) with true value. 
5) Current_number = index + 2; 
6) Continue steps 3-5 until search is finished. 

該算法需要O（nloglogn）時間。 你做的實際上需要更多的時間（O（n^2））。 順便說一句，在第二步中（您在n和m之間搜索素數），您不必檢查這些數字是否爲質數，理想情況下，您將在算法的第一階段計算它們。

正如我在網站上看到的，你鏈接的主要問題是你實際上不能創建一個大小爲n-1的數組，因爲最大數n是10^9，如果你這樣做的話會導致內存問題天真的方式。這個問題是你的:)

Answer 5

我不確定你是否實施了Erasthotenes篩。無論如何，有幾件事可能會加快你的算法的速度：通過預先分配空間避免多次重新分配矢量內容（查找std::vector<>::reserve）。操作sqrt是昂貴的，你也許可以通過修改測試，完全避免（停止時x*x > y，而不是檢查x < sqrt(y)。

再然後，你將修改實際的算法得到了更好的改善。從走馬看起來好像你在迭代所有的候選人和每個候選人，試圖用所有已知的素數進行分解，這些素數可能是因素。Erasthotenes的篩選單一素數並且一次丟棄所有素數的倍數

請注意，篩沒有執行任何操作來測試一個數是否爲素數，如果它在這之前沒有被丟棄，那麼它是素數，每個非素數只被訪問一次f或每個獨特的因素。另一方面，您的算法正在多次處理每個數字（針對現有的素數）

Answer 6

我理解問題的方式是必須生成範圍[m，n]中的所有素數。

不需要計算[0，n]中的所有素數就可以做到這一點，因爲這很可能是減慢你的速度，首先是生成[0，sqrt（n）]範圍內的所有素數。

然後使用結果篩選範圍[m，n]。要生成素數的初始列表，請執行Eratosthenes篩選的基本版本（從維基百科文章中的僞代碼幾乎只是一個簡單的實現就可以做到這一點）。

這應該使您能夠在很短的時間內解決問題。

這裏的埃拉託塞尼的篩的一個簡單的示例實施：

std::vector<unsigned> sieve(unsigned n) { 
    std::vector<bool> v(limit, true); //Will be used for testing numbers 
    std::vector<unsigned> p;   //Will hold the prime numbers 

    for(unsigned i = 2; i < n; ++i) { 
     if(v[i]) {     //Found a prime number 
      p.push_back(i);    //Stuff it into our list 

      for(unsigned j = i + i; j < n; j += i) { 
       v[i] = false;   //Isn't a prime/Is composite 
      } 
     } 
    } 

    return p; 
} 

它返回只包含從0到n素數的向量。然後你可以用它來實現我提到的方法。現在，我不會爲你提供實現，但是，你基本上必須做與Eratosthenes篩選相同的事情，但不是使用所有整數[2，n]，而是使用你找到的結果。不知道這是否放棄太多？

Answer 7

由於在原來的問題SPOJ problem沒有規定它必須與埃拉托色尼的篩來解決，這裏的基礎上this article的替代解決方案。在我六歲的筆記本電腦上，它運行時間約爲15毫秒，用於最差的單個測試案例（n-m = 100,000）。

#include <set> 
#include <iostream> 

using namespace std; 

int gcd(int a, int b) { 
    while (true) { 
     a = a % b; 

     if(a == 0) 
     return b; 

     b = b % a; 

     if(b == 0) 
     return a; 
    } 
} 

/** 
* Here is Rowland's formula. We define a(1) = 7, and for n >= 2 we set 
* 
* a(n) = a(n-1) + gcd(n,a(n-1)). 
* 
* Here "gcd" means the greatest common divisor. So, for example, we find 
* a(2) = a(1) + gcd(2,7) = 8. The prime generator is then a(n) - a(n-1), 
* the so-called first differences of the original sequence. 
*/ 
void find_primes(int start, int end, set<int>* primes) { 
    int an;  // a(n) 
    int anm1 = 7; // a(n-1) 
    int diff; 

    for (int n = start; n < end; n++) { 
     an = anm1 + gcd(n, anm1); 

     diff = an - anm1; 

     if (diff > 1) 
     primes->insert(diff); 

     anm1 = an; 
    } 
} 

int main() { 
    const int end = 100000; 
    const int start = 2; 

    set<int> primes; 

    find_primes(start, end, &primes); 
    ticks = GetTickCount() - ticks; 

    cout << "Found " << primes.size() << " primes:" << endl; 

    set<int>::iterator iter = primes.begin(); 
    for (; iter != primes.end(); ++iter) 
     cout << *iter << endl; 
}