打印素數小於100

Question

可能重複：
Which is the fastest algorithm to find prime numbers?

有沒有什麼辦法，使這更優化..

#include <vector> 
    int main() 
    { 
     std::vector<int> primes; 
     primes.push_back(2); 
     for(int i=3; i < 100; i++) 
     { 
      bool prime=true; 
      for(int j=0;j<primes.size() && primes[j]*primes[j] <= i;j++) 
      { 
       if(i % primes[j] == 0) 
       { 
        prime=false; 
        break; 
       } 
      } 
      if(prime) 
      { 
       primes.push_back(i); 
       cout << i << " "; 
      } 
     } 

     return 0; 
    } 

Answer 1

Sieve of Eratosthenes是一個偉大的算法用於產生一定數量的素數（這不是你的標題所指出的，b你的代碼暗示了什麼）。

Answer 2

是的，將i++更改爲i+=2，它的工作速度會提高一倍。

Answer 3

int main(int argc, char *argv[]) { 
    cout << "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 "; 
} 

:-)

更嚴重的是，你能避免緩存primes[j] * primes[j]反覆平方素數，節省乘法。

Answer 4

1. 不做primes[j]*primes[j] <= i只是檢查primes[j] <= 7
2. 使用i+=2

Answer 5

是。正如Marion所建議的那樣，您可以使用Sieve of Eratosthenes，但您應該瞭解詳細信息。你寫的代碼看起來像篩子，但事實並非如此。它被稱爲審判分裂，它有不同於篩子的algorithmic complexity。

篩子執行每個素數p需要Theta(n/p)時間的合格。這導致總複雜度爲O(n log log n)。 IIRC證明有點複雜，涉及prime number theorem。

您的算法對每個素數p執行pi(sqrt(p))除法，對於非素數執行較小數目的除法。 （其中pi是prime-counting function）。不幸的是，我無法想出完全的複雜性。

簡而言之，您應該更改代碼以使用數組並標記所有非素數。 This article解決了函數式編程語言中的相同主題。

Answer 6

是的，Eratosthenes篩是最好​​的選擇（如果你需要100個以上的號碼this是最好的實施）。這是我的實現：

#include <vector> 
#include <iostream> 
#include <cmath> 
using namespace std; 

vector<int> sieve(int n){ 
    vector<bool> prime(n+1,true); 
    vector<int> res; 
    prime[0]=prime[1]=false; 
    int m = (int)sqrt(n); 
    for(int i=2; i<=m; i++){ 
     if(prime[i]) 
      for(int k=i*i; k<=n; k+=i) 
       prime[k]=false; 
    } 
    for(int i=0; i<n ;i++) 
     if(prime[i]) 
      res.push_back(i); 
    return res; 
} 

int main(){ 
    vector<int> primes = sieve(100); 
    for(int i=0; i<primes.size() ;i++){ 
     if(i) cout<<", "; 
     if(primes[i]) cout<<i; 
    } 
    cout<<endl; 
}