首先，得需要知道什么是“素数”。素数也是质数，根据百度所说：

质数是指在大于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;
}

long long p[maxn],e[maxn];
bool hash[maxn];
void init()
{
		memset(hash,0,sizeof(hash));
		memset(hash,0,sizeof(e));
    long long i, j;
    
    p[0] = 1; //记录素数个数
    p[1] = 2;
    for (i=3; i<N; i+=2)
    {
        if (hash[i])
            continue;
        p[++p[0]] = i;
        for (j=i*i; j<N; j+=i)
            hash[j] = true;
    } //筛素数
    
    e[1] = 1;

    for (i=1; i<=p[0]; i++)
        e[p[i]] = p[i] - 1; //初始化素数的phi

    for (i=2; i<N; i++)
    {
        if(!e[i])
        {
            for (j=1; j<=p[0]; j++)
                if (i % p[j]==0)
                {
                    if (i / p[j] % p[j])
                        e[i] = e[i / p[j]] * e[p[j]];
                    else
                        e[i] = e[i / p[j] ]* p[j];
                    break;
                } // 利用上述性质求解
        }        
    }
    return ;
}

求10000以内的所有素数，这个问题可以使用线性欧拉筛选法，时间复杂度为O(n),上代码：
public class EulerSieve {

	static boolean[] flag = new boolean[10001];
	static int[] prime = new int[10001];

	public static void main(String[] args) {
		eulerSieve();
		int count = 0;
		for (int i = 0; i < prime.length; i++) {
			if (prime[i] != 0) {
				System.out.println(prime[i]);
				count++;
			}
		}
		System.out.println("一共有" + count + "个素数");
	}

	public static void eulerSieve() {
		int count = 0;
		for (int i = 2; i < flag.length; i++) {
			if (!flag[i]) {
				prime[count++] = i;
			}
			for (int j = 0; j < count && i * prime[j] < flag.length; j++) {
				flag[prime[j] * i] = true;
				if (i % prime[j] == 0) { //重要！
					break;
				}
			}
		}
	}

}


运行结果：



最重要的就是break的逻辑，首先，不论一个数i是否是素数，都要用素数乘这个数来筛选掉合数，什么时候停止呢，就是i是某个素数的倍数的时候，为什么呢，详细解释，如果i%prime[j]=0,那么假设i=prime[j]乘k,即n=prime[j+1]乘i = prime[j+1]乘prime[j]乘k=prime[j]乘m

即n这个非素数可以用prime[j]来筛选，所以不需要拿更大的素数来筛选，所以break。

举个简单的例子，当遍历到4时，我们用2乘4筛选掉8，接下来还需要接着用3乘4筛选掉12吗？不需要了，因为我们可以用2乘6筛选掉12，如果我们用3乘4来筛选了，那遍历到6时，再用2乘6筛选，结果不会有错，但时间复杂度增加了。所以这里最关键的一点是，对于每一个合数，我们都是用它的最小质因子来筛选掉它的。所以时间复杂度为O（n）。