素数筛法（判断一个数是否为素数，以及一个区间所有素数）

判断素数：
我们只需测试到不比 sqrt（n）（对n开根号）大的整数即可，若到这个整数为止，所有正整数数均不能整除 n，则可以断定， n 为素数。

int bound = (int) sqrt(x) + 1; //计算枚举上界 ,为防止 double值带来的精度损失 , 
所以采用根号值取整后再加 1,即宁愿多枚举一个数也不能少枚举一个数

判断一个区间所有素数
在我们获得一个素数时，即将它的所有倍数均标记成非素数，这样当我们遍历到一个数时，它没有被任何小于它的素数标记为非素数，则我们确定其为素数。
题目描述：
输入一个整数 n(2<=n<=10000)，要求输出所有从 1 到这个整数之间 (不包括
1 和这个整数 )个位为 1 的素数，如果没有则输出 -1。
输入：
输入有多组数据。
每组一行，输入 n。
输出：
输出所有从 1 到这个整数之间 (不包括 1 和这个整数 )个位为 1 的素数 (素数之
间用空格隔开，最后一个素数后面没有空格 )，如果没有则输出 -1。
样例输入：
100
样例输出：
11 31 41 61 71
来源：
2008 年北京航空航天大学计算机研究生机试真题

#include <stdio.h> 
int prime[10000]; //保存筛得的素数
int primeSize; //保存的素数的个数
bool mark [10001]; //若mark[x] 为true,则表示该数 x已被标记成非素数
void init() { //素数筛法
for (int i = 1;i <= 10000;i ++) { 
mark [i] = false; 
} //初始化，所有数字均没被标记
primeSize = 0; //得到的素数个数为 0 
for (int i = 2;i <= 10000;i ++) { //依次遍历 2到10000所有数字
if (mark [i] == true) continue; //若该数字已经被标记 ,则跳过
prime[primeSize ++] = i; //否则 ,又新得到一个新素数
for (int j = i * i;j <= 10000;j += i) { //并将该数的所有倍数均标记成非
素数
mark [j] = true; 
} 
} 
} 
int main () { 
init(); //在程序一开始首先取得 2到10000中所有素数
int n; 
while (scanf ("%d" ,& n) != EOF ) { 
bool isOutput = false; //表示是否输出了符合条件的数字
for (int i = 0;i < primeSize;i ++) { //依次遍历得到的所有素数
if (prime[i] < n && prime [i] % 10 == 1) { //测试当前素数是否符合条
件
if (isOutput == false) { //若当前输出为第一个输出的数字 ,则标记已
经输出了符合条件的数字 ,且该数字前不输出空格
isOutput = true; 
printf ("%d" ,prime[i]); 
} 
else printf (" %d" ,prime[i]); //否则在输出这个数字前输出一个空格
} 
} 
if (isOutput == false) { //若始终不存在符合条件的数字
printf ("-1\n" ); //输出 -1并换行
} 
else printf ("\n" ); //换行
} 
return 0; 
}

筛法中我们使用了一个小技巧。当我们判定 i 为素数，要标记其所有倍数为非素数时，我们并没有从 2 * i 开始标记，而是直接从 i * i 开始标记。其原因是显然的， i * k （k < i）必已经在求得 k 的某个素因数（必小于 i）时被标记过了，即 i*k 同时也是 k 的素因数的倍数。所以这里，我们可以直接从 i 的平方开始标记起。