查找质数的个数（C++）埃氏筛法（Sieve of Eratosthenes）

问题描述：输入一个数字n，求0-n中所有的质数的个数

思路如下：

1. 创建一个 bool 类型的数组 isPrime，数组大小为 n+1，用来标记每个数是否为质数。初始时，将所有的元素都置为 1。
2. 从 2 开始枚举到 n，如果当前数 i 是质数，则将其所有的倍数都标记为合数（将对应的 isPrime 数组中的值置为 0）。
3. 统计 isPrime 数组中值为 true 的元素个数，即为 n 以内质数的个数。 

下面是代码求解：

#include<iostream>
#include<vector> 
using namespace std;

void show(vector<int> temp,int length){
	for(int i=0;i<length;i++){
		printf("%d\n",temp[i]);
	}
}
int countPrimes(int n){
	//定义一个vector容器 ，所有值初始化为1 
	vector<int> isPrime(n+1,1);
	//定义一个变量count来统计质数的数量 
	int count=0;
	//这里要从2开始枚举，将其所有的倍数标记为合数 
	for(int i=2;i<n;i++){
		if(isPrime[i]){
			count++;
		}
		for(int j=2*i;j<n;j+=i){
			isPrime[j]=0;
		}
	}
	show(isPrime,n+1);
	return count;
}

int main(){
	int n; 
	int count;
	printf("请输入一个数n:"); 
	scanf("%d",&n);
	count=countPrimes(n);
	printf("%d\n",count);

}