Eratosthenes的筛C++

目前我正在一个项目，我想计算所有素数。当我编译（MINGW Windows Comp。）时，程序崩溃并返回一个随机错误号。这是我写的代码：此时Eratosthenes的筛C++

/* 
    Sieb des Eratosthenes 
*/ 

#include <iostream> 
#include <math.h> 
using namespace std; 

main() 
{ 
    //variablendeklaration 
    unsigned int nmax=100; 
    unsigned int i,j,erg; 
    bool prim[nmax]; 

    //Initialisieren 
    prim[0]=false; 
    prim[1]=false; 

    //array prim[i] erstellen 
    for(i=2;i<nmax;i++) 
    { 
     prim[i]=true; 
    } 




    for(i=2;i<nmax;i++) //alle Primzahlen durchlaufen 
    { 
     if(prim[i] == true) //auf Prim prüfen 
     { 
      for(j=2;j<nmax;j++) //multiplizieren und wegstreichen 
      { 
       erg = j * i; 
       prim[erg] = false; 
      } 
     } 
    } 

    for(i=2;i<nmax;i++) 
    { 
     cout << prim[i] << endl; 
    } 


}

来源

2013-10-03 benni

除非你被禁止 - 使用矢量代替 - '矢量素数; –

当您开始使用相当大的数字时（例如> 100万），这个O（n^2）版本的筛子将永远持续下去。 –

：你会

  erg = j * i; 
      prim[erg] = false;

最终获得超越prim的范围，因为这两种i和j可以具有高达nmax - 1的值，因此erg将具有最大值(nmax - 1) * (nmax - 1)。您需要检查这种情况，如果erg >= nmax，例如

  erg = j * i; 
      if (erg < nmax)   // if i * j still within bounds 
       prim[erg] = false; // set prim[i * j] to false 
      else      // else i * j now >= nmax 
       break;    // break out of loop and try next i value

来源

2013-10-03 18:31:22

这是什么意思？我是否必须更改for循环中的var“nmax”？ – benni

不 - 只需更改上述代码即可。 –

是的，非常感谢，它为我工作！ – benni

另一种方式来解决这个问题是为了避免在循环额外的步骤：

for(i=2; i < nmax; i++) 
{ 
    if(prim[i] == true) 
    { 
     for (j = 2 * i; j < nmax; j += i) // state j at 2i, increment by i 
     { 
      prim[j] = false; 
     } 
    } 
}

这样做的效果1）通过嵌套nmax项目不循环（降低你的整体复杂度从O（ n^2）到O（n *（n/2 + n/6 + n/10 + ...），这实际上是O（n log n），并且2）不需要额外的边界检查，因为你永远不会在你的循环条件下越界越好

来源

2013-10-03 19:26:04

Eratosthenes的筛C++

回答

相关问题