素数筛选法(prime seive)

时间：2023-03-09 00:46:38
素数筛选法(prime seive)

素数筛选法比较有名的,较常用的是Sieve of Eratosthenes,为古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。详细步骤及图示讲解,还有java与c++版源代码.

 void runEratosthenesSieve(int upperBound) {

     int upperBoundSquareRoot = (int)sqrt((double)upperBound);

     bool *isComposite = new bool[upperBound + ];

     memset(isComposite, , sizeof(bool) * (upperBound + ));

     for (int m = ; m <= upperBoundSquareRoot; m++) {

         if (!isComposite[m]) {

             for (int k = m * m; k <= upperBound; k += m)

                 isComposite[k] = true;

         }

     }

     for (int m = ; m <= upperBound; m++)

         if (!isComposite[m])

             cout << m << " ";

     delete [] isComposite;

 }

素数在信息安全中有着重要应用.

相关文章