### 输出 1...200 之间的素数

素数理论在计算机领域有着广泛的应用，它主要体现在一些优秀的算法实现。例如，1980 年，图灵奖获得者 Karp 和 Rabin 教授运用素数理论和概率论设计出了一种新的字符串比配算法，简称为 KR 算法。在本题目中，只是要求简单的输出 200 以内的素数。核心问题就是素数的判断。我们在小学时就知道什么是素数。除了 1 和素数本身之外，它不能够整除其他数。例如，1、2、 3、5 、7、11 等都是素数。在程序中实现素数的遍历，首先需要对数值 n 进行开方运算 V，然后遍历 2…V 之间的整数，如果某一个数能够与数值 n 进行整除，则该数值 n 为非素数。如果 2…V 之间的所有整数都不能与数值 n 进行整除，则数值 n 是素数。

答案

bool EnumPrimeNum(const int max) //判断素数

{

int isqr = (int)sqrt(max); //开方计算

int *pvar = new int[isqr]; //构建一个数组

for (int j=0; j<isqr; j++) //设置数组元素为 1…max 的开平方

pvar[j] = 0;

int i = 2;

bool ret = true;

while (ret && i <= (int)sqrt(max)) //遍历 1…max 的开平方

{

if (pvar[i-2]==0)

{

if (max % i ==0)

ret = false;

else

{

int next = i + i;

while (next < (int)sqrt(max))

{

pvar[next-2] = 1;

next += i;

}

}

}

i++;

}

delete []pvar; //释放数组

return ret;

}

int main(int argc, char* argv[])

{

int num = 200;

int counter = 0;

for(int i = 2; i< num; i++) //遍历 2…200

if (EnumPrimeNum(i)) //判断是否为素数

{

counter++;

printf("%4d",i); //输出素数

if (counter % 10 == 0)

printf("\n");

}

printf("\n");

return 0;

}

效果如图 1 所示。

图 1 1…200 之间的素数