埃氏筛选法---打印素数表_埃氏筛法打素数表

思想：算法从小到大枚举所有数，对于每一个素数，筛去它的所有倍数，剩下的就是素数
对于n在10^5以内的可以使用isPrime()进行判断，但是对于需要更大范围的素数表，可以使用该方法

代码核心实现

//素数筛选法代码
const int maxn=101;//表长
int prime[maxn],num;//prime数组 存放所有的素数，num为素数个数
bool p[maxn]={0};//如果i为素数，则p[i]为false,否则，p[i]为true
void Find_Prime()
{
    for(int i=2;i<maxn;i++)//从2开始 ，注意循环条件不能写成i<=maxn
    {
        if(p[i]==false)//如果p[i]是素数
        {
            prime[num++]=i;//把素数i存放在prime数组中
            for(int j=i+i;j<maxn;j+=i)//筛去所有i的倍数，循环条件不能写成j<=maxn
            {
                p[j]=true;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18