首先，得需要知道什么是“素数”。素数也是质数，根据百度所说：
质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
而欧拉筛选则用到数组和两个for循环（应该吧，我也在学习中，所以标题有个“1”）

//欧拉筛选素数法 
#include <stdio.h>

int ys[2500001]={0};//值为0表示是素数 

int main()
{ 
	int i,j,a,b,max=0,t;
	
	for(i=2;i<=2500000;i++)
	{
		if(ys[i]==0)//i的素数状态为0，表示i为素数 
			for(j=i+i;j<=2500000;j=j+i)//j的变化范围所有i的倍数,也就是说i是j的约数
				ys[j]=1;//将j的素数状态置为1，表是j不是素数 
	}	
	
	for(i=2;i<=1000;i++)
		if(ys[i]==0)
		{
			printf("%d,",i);
		}
	return 0;
}

这是我们老师上课给我们展示的代码，大概的思路是：
设定一个等于0的数组，0代表为素数，代码中的2和2500000可以自己输入修改，
写第一个for循环，目的是将数据内所有包含的数都拿出来一遍，
如果数组内为0就继续，如果为一就直接跳过
第二个循环，让j等于两倍i，并且每次循环加上一个i（据说原本应该是乘的，但乘的话太容易越界了）每一次循环就让这个数对应的数组内等于1，因为j始终是i的倍数，所以j始终不是素数。
这样很快所有非素数的数组内就为1了
接下来只需要输出数组为0的就可以了。

1、素数筛选法（时间复杂度O(nloglogN)

/*
    素数判断：素数筛选法（用素数筛选合数）
*/
#include <stdio.h>
#include <math.h>
#define MAX_N 100

//素数筛选法
int prime[MAX_N + 5] = {0};//初始化为0
void init() { //素数筛选法
    for(int i=2;i<=MAX_N;i++) {
        if(!prime[i]) {//素数时
            prime[++prime[0]] = i;//prime[0]记录素数的个数，后面的依次储存素数
            for(int j=i*i;j<=MAX_N;j+=i) { //此素数的倍数必为合数（可以不必从2*i开始筛）
                prime[j] = 1;//筛去
            }
        }
    }
}
int main() {
    init();
    printf("prime[0]:%d\n",prime[0]);
    for(int i=1;i<=prime[0];i++) {
        printf("%d ",prime[i]);
    }
    printf("\n");
    return 0;
}

2、应用：求1~n中每个数的最小素因子

/*
    求2~n内每个数的最小素因子
*/
#include <stdio.h>
#include <math.h>
#define MAX_N 100
int prime[MAX_N + 5] = {0};//初始化为0
void init() { 
    for(int i=2;i<=MAX_N;i++) {
        if(!prime[i]) {
            prime[i] = i; //素数的最小素因子为她本身
            for(int j=2*i;j<=MAX_N;j+=i) {//可以令j从i开始循环，这样可以省略上面那句话 
                if(!prime[j])
                    prime[j] = i;
            }
        }
    }
}
int main() {
    init();
    for(int i=2;i<MAX_N;i++) {
        printf("MIN_factory[%d] = %d\n",i,prime[i]);
    }
    return 0;
}

3、线性筛选（欧拉筛选，时间复杂度O(n)）

/*
    素数判断：线性筛选
*/
#include <stdio.h>
#include <math.h>
#define MAX_N 100

//线性筛选（欧拉筛选）
int prime[MAX_N + 5] = {0};//初始化为0
void init() { 
    for(int i=2;i<=MAX_N;i++) {
        if(!prime[i]) {
            prime[++prime[0]] = i; //prime[0]记录素数的个数，后面依次储存素数（从prime[1]开始
        }
        for(int j=1;j<=prime[0];j++) {
            if(i*prime[j] > MAX_N) break;//只需标记MAX_N以内的素数
            prime[i*prime[j]] = 1;
            if(i%prime[j] == 0) break;//关键步骤，避免重复筛选
        }
    }
}
int main() {
    init();
    for(int i=1;i<=prime[0];i++) {
        printf("%d ",prime[i]);
    }
    printf("\n");
    return 0;
}

4、应用，求第10001个素数

/*
    求第10001个素数
*/
#include <stdio.h>
#include <math.h>
#define MAX_N 200000

//线性筛选（欧拉筛选）
int prime[MAX_N + 5] = {0};//初始化为0
void init() { 
    for(int i=2;i<=MAX_N;i++) {
        if(!prime[i]) {
            prime[++prime[0]] = i; //prime[0]记录素数的个数，后面依次储存素数（从prime[1]开始
        }
        for(int j=1;j<=prime[0];j++) {
            if(i*prime[j] > MAX_N) break;//只需标记MAX_N以内的素数
            prime[i*prime[j]] = 1;
            if(i%prime[j] == 0) break;//关键步骤，避免重复筛选
        }
    }
}
int main() {
    init();
    printf("%d\n",prime[10001]);
    return 0;
}

答案是：104743

5、应用，求2~N内每个数的质因数个数

/*
    求2~N内每个素的质因数个数,如2的质因数个数为2（1，2），4的质因数个数为3（1，2，4）
*/


#include <iostream>
#include <stdio.h>
using namespace std;

#define MAX_N 100
int prime[MAX_N+5] = {0};
int factory_cnt[MAX_N] = {0};
void init() {
    //前半部分是线性筛选，后半部分是质因数分解定理
    for(int i=2;i<=MAX_N;i++) {
        if(!prime[i]) 
            prime[++prime[0]] = i;

        for(int j=1;j<prime[0];j++) {
            if(i*prime[j] > MAX_N) break;
            prime[i*prime[j]] = 1;
            if(i%prime[j]==0) break;
        }

        int tem = i;
        int j = 1;
        int cnt ,ans = 1;
        while(tem!=1) {
            cnt = 0;
            while(tem%prime[j]==0) {
                cnt++;
                tem /= prime[j];
            }
            ans *= (1+cnt);
            j++;
        }
        factory_cnt[i] = ans;
    }
}

int main() {
    init();
    for(int i=2;i<=MAX_N;i++) {
        printf("%d ",factory_cnt[i]);
    }
    printf("\n");
}

输出

2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 2 6 2 6 4 4 2 8 3 4 4 6 2 8 2 6 4 4 4 9 2 4 4 8 2 8 2 6 6 4 2 10 3 6 4 6 2 8 4 8 4 4 2 12 2 4 6 7 4 8 2 6 4 8 2 12 2 4 6 6 4 8 2 10 5 4 2 12 4 4 4 8 2 12 4 6 4 4 4 12 2 6 6 9

更好的解法

#include <iostream>
#include <memory.h>
using namespace std;

int main() {
    int m,n;
    cin>>m>>n;
    int * prime = new int[n+1];
    int *cnt = new int[n+1];
    int *fac = new int[n+1];
    memset(prime,0,sizeof(int)*(n+1));
    memset(cnt,0,sizeof(int)*(n+1));//储存最小因子的个数
    memset(fac,0,sizeof(int)*(n+1));//储存因子个数
    for(int i=2;i<=n;i++) {
        if(!prime[i]) {
            prime[++prime[0]] = i;
            fac[i] = 2;
            cnt[i] = 1;
        }
        for(int j=1;j<=prime[0];j++) {
            if(i*prime[j] > n)  break;
            prime[i*prime[j]] = 1;
            if(i%prime[j]==0) {
                fac[i*prime[j]] = fac[i]/(cnt[i]+1)*(cnt[i]+2);
                cnt[i*prime[j]] = cnt[i] + 1;
                break;
            }else {
                fac[i*prime[j]] = fac[i]*fac[prime[j]];
                cnt[i*prime[j]] = 1;
            }
        }
    }
    for(int i=m;i<=n;i++) {
        cout<<fac[i]<<"\n";
    }
    delete[] prime;
    delete[] cnt;
    delete[] fac;
}

既然你点进来，那一定让你懂的出去
概念
素数（也称质数):只有1和它本身两个因数的自然数
合数：合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数
欧拉筛法的精髓就在于每个合数只筛了一次
（所以时间复杂度接近于O（n）

给出一个式子（相信您在其他地方已经看到过，或看到过类似的
这个式子非常重要
“最小质因数 × 最大因数（非这个合数） = 这个合数”

先看一下板子

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxx=100000000+10;
int s[6000000+10];//存素数
bool  isprime[maxx];//如果是合数标记为1，是素数标0
int main(){
	int n;//n为范围
	std::ios::sync_with_stdio(0);//优化
	cin>>n;
	int top=1;
	memset(isprime,1,sizeof(isprime));
	isprime[1]=0;
	for(int i=2;i<=n;++i){
		if(isprime[i])
			s[top++]=i;//
		for(int j=1;j<=top && i*s[j]<=n/*i*s[j]不能超出求值得范围*/;++j){
			isprime[i*s[j]]=0;//i*s[j]一定为合数
			if(i%s[j]==0) break;//后面解释
		}
	}
	for(int i=2;i<=top;++i) cout<<s[i]<<" ";
	return 0;
} 

其实核心代码就几行

for(int i=2;i<=n;++i){
		if(isprime[i])
			s[top++]=i;
		for(int j=1;j<=top && i*s[j]<=n;++j){
			isprime[i*s[j]]=0;
			if(i%s[j]==0) break;
		}
	}

我们拆分出来一个一个理解

if(isprime[i])
			s[top++]=i; 

经过前i-2次的筛选（因为是从i=2开始筛，并且这个i还没有筛掉）后，这个i值还没有被筛掉，那它一定是素数

简单来说就是 此时i之前的 i和 s[j] 没有一个是当前这个数的因数

		for(int j=1;j<=top && i*s[j]<=n;++j){

i*s[j]<=n的原因是保证筛选的合数在n的范围内
因为求的素数是<=n，所以也没必要再筛掉大于n的

isprime[i*s[j]]=0;
if(i%s[j]==0) break;

这两行合着一起讲

最小质因数 × 最大因数（非这个合数） = 这个合数
通过这个式子就能表示出一个合数

i*s[j]=某个合数

s[j]是最小的质因数，i是最大因数

那么如何保证是s[j]是最小质因数了
这行代码的作用就来了

if(i%s[j]==0) break;可谓是神来之笔

证明：
假设p=s[j]是合数c的最小质因数（s数组存放素数，且单调递增的

当i%p== 0时,c== p* i==p* p *( i/p);

因为c是定值

如果这时p1=s[j+1]了

令d=i*p1，c!=d；//说明筛的不是同一个合数

而d=i*p1=s[j] * (i/s[j]) *p1

又因为s[j]<p1==s[j+1]

所以d的最小质因数应该是s[j]而不是s[j+1]

所以d的最大因数应该是 (i/s[j]) * p1

又因为 (i/s[j]) * p1>i

所以不在当前i%s[j]==0时停止，就会使后面的某个i*s[j]重复筛
而欧拉筛的要求就在于不能重复筛

综上所以需要到i%s[j]== 0时，枚举下一个最小质因数为s[j+1]的数
（数学反证法）

附赠一道练习题

有什么疑惑意见可以发出来互相交流

谢谢观赏