先来举个简单的例子来介绍一下“筛法”，求2~20的质数，它的做法是先把2~20这些数一字排开：
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
先取出数组中最小的数，是2，则判断2是质数，把后面2的倍数全部删掉。
2 | 3 5 7 9 11 13 15 17 19
接下来的最小数是3，取出，再删掉3的倍数
2 3 | 5 7 11 13 17 19
一直这样下去，直到结束。剩下的数都是素数。
int main()
{
int notPrime[100] = { 0 };
/* 下标筛选法求质数数组 */
notPrime[0] = 1;
notPrime[1] = 1;
for (long i = 2; i < 100; ++i) {
if (!notPrime[i]) {
for (long j = 2; i * j < 100; ++j) {
notPrime[i * j] = 1;
}
}
}
for (int i=0; i < 100; ++i)
{
cout << i << "--" << notPrime[i] << endl;
}
}
转载请注明原文地址: https://ju.6miu.com/read-1124626.html
