打印素数小于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; 
}