素数筛选法(prime seive)

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

 1 void runEratosthenesSieve(int upperBound) {
 2     int upperBoundSquareRoot = (int)sqrt((double)upperBound);
 3     bool *isComposite = new bool[upperBound + 1];
 4     memset(isComposite, 0, sizeof(bool) * (upperBound + 1));
 5     for (int m = 2; m <= upperBoundSquareRoot; m++) {
 6         if (!isComposite[m]) {
 7             for (int k = m * m; k <= upperBound; k += m)
 8                 isComposite[k] = true;
 9         }
10     }
11     for (int m = 2; m <= upperBound; m++)
12         if (!isComposite[m])
13             cout << m << " ";
14     delete [] isComposite;
15 }

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