筛选法求n以内素数（质数）

---

• 判断一个数是不是素数，可以用 2 到 $\sqrt{n}$n​ 之间的所有整数去除 n，看能否整除。如果都不能整除，那么 n 是素数（慢！）
• 筛法求素数：把 2 到 n 中所有的数都列出来，然后从 2 开始，先划掉 n 以内的所有 2 的倍数，然后每次从下一个剩下的数（必然是素数）开始，划掉其 n 内的所有倍数。最后剩下的数，就都是素数。（空间换时间，提高了运算速度）

---

1. 设置一个标志数组 isPrime，isPrime[ i ] 的值是 1 就表示 i 是素数。开始数组元素值全部为 1
2. 划掉 k 的倍数，就是把 isPrime[ 2*k ]，isPrime[ 3*k ] …置成 0
3. 最后检查 isPrime 数组，输出 isPrime[ i ] 为 1 的那些 i

---

#include <iostream>
#include <cstdio>
using namespace std;
#define max_num 1000000
char isPrime[max_num+10];	//最终如果isPrime[i]为1，则表示i是素数 
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;
	}
	return 0;
}

第 5 行代码定义一个 char 类型的数组即可存放 0 1。因为节约内存空间。

---