筛选法求n以内素数

判断一个数n是不是素数，可以用2到 根号n之间的所有整数去除n，看能否整除。如果都不能整除，那么n是素数(慢）。 筛选法求素数：把2到n中所有的数都列出来，然后从2开始，先划掉n内所有2的倍数，然后每次从下一个剩下的数(必然是素数)开始，划掉其n内的所有倍数。最后剩下的数，就都是素数。 空间换时间，加快了计算速度。 代码如下：

#include //筛法求素数
#include
using namespace std;

int MAX_NUM = 100;
char isPrime[101]; //最终如果isPrime[i]为1，则表示i是素数,之所以加1是因为我们有100个数字，而数组从0开始

int main()
{
for (int i = 2; i <= MAX_NUM; ++i) //开始假设所有数都是素数
isPrime[i] = 1;

for (int i = 2; i <= MAX\_NUM; ++i) //每次将一个素数的所有倍数标记为非素数 
{        
    if (isPrime\[i\])    //只标记素数的倍数
        for (int j = 2 \* i; j <= MAX\_NUM; j += i)
            isPrime\[j\] = 0;    //将素数 i 的倍数标记为非素数
}

for( int i = 2;i <= MAX\_NUM; ++i)
    if( isPrime\[i\]) 
        cout << i << endl;

system("pause");
return 0;

}