埃拉托斯特尼筛法，也称为埃氏筛法（Sieve of Eratosthenes），是一种用于计算素数的古老而经典的算法。它由古希腊数学家埃拉托斯特尼（Eratosthenes）在公元前3世纪提出。
该算法的基本思想是从小到大遍历每个数字，并将其所有的倍数标记为非质数。通过不断排除合数的方式，最终得到所有的素数。
以下是埃拉托斯特尼筛法的基本步骤：
创建一个布尔类型的数组，表示范围内的所有数字。初始时将数组中所有元素标记为"true"，表示都是素数。
从2开始，遍历数组中的每个数。如果当前数字被标记为素数（即为"true"），则进行下一步；否则，跳过该数字。
对于当前素数p，从p的平方开始，将p的倍数（2p、3p、4p等）标记为合数（即为"false"）。
继续向后遍历，重复步骤2和步骤3，直到遍历完整个范围。
遍历结束后，所有未被标记为合数（仍为"true"）的数字都是素数。
使用埃拉托斯特尼筛法可以高效地找出一定范围内的素数。该算法的时间复杂度为O(nloglogn)，其中n为范围的大小。
代码语言：javascript复制//埃拉托斯特尼筛法
#include <vector>
int main()
{
int n = 0;
cin >> n;
vector<bool> b(n 1, true);
for (int i = 2; i*i <= n 1; i)
{
if (b[i])
{
for (int j = i * i; j < n 1; j = i)
{
b[j]=false;
}
}
}
int count = 0;
for (int i = 2; i < b.size(); i )
{
if (b[i])
count ;
}
cout << count << endl;
return 0;
}
