用筛法求100以内的全部素数

用筛法求100以内的全部素数，并按每行五个数显示

基本思路

① 将布尔类型的空数组全置为true，表示每个数组的数还未被剔除
② 1不是素数，被剔除，故置为false
③ 数组大小101，且下标与自然数2到100依依对应
④ 每次都已最小数为基准，然后不断递增乘其倍数（两倍、三倍、四倍……），找出以该基准数为因数的非素数，并且置为false，表示剔除。等循环至n的平方根处便停止，从而找到所有素数

代码如下

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
const int n = 100;
int t;
bool a[n + 1];

int main() {
	//数组全赋值为1，表示该下标上的数存在 
	for (int i = 0; i <= n; i++) {
		a[i] = true;
	}
	a[1] = false;
	//从2开始，不断摘出其倍数的下标，将其赋值为0，以示非素数被摘除 
	for (int i = 2; i <= sqrt(n); i++) {
		if (a[i]) {
			for (int j = 2; j <= n / i; j++) {
				a[i * j] = false;
			}
		} 
	}
	
	t = 0; 
	for (int i = 2; i <= n; i++) {
		if (a[i]) {
			cout << setw(5) << i;
			t++;
			if (t % 5 == 0) {
				cout << endl;
			}
		} 
	}
	
	return 0;
}

运行结果