在开筛之前，我们要理解一个很好理解的概念，任何一个合数可以拆成一个最小素数和另一个数（可能质数可能合数）的乘积
这个最小素数即为这个合数的最小质因子
//比如 12=2*6，此时2就是12的最小质因子，当然亦有12=3*4，可以看到3也是12的质因子，但不是最小的质因子
//而且，对于一合数a=b*q，b为a的最小质因子，a只有一种分解方法，也就是说，对于a，它仅能被最小素因子整除，也就是说，a只能被b筛选一次
//而欧拉筛正是用最小质因子来筛掉合数的，对于一个数，我们遍历他的素数倍（这里的素数是已经找到的素数），将其标记为合数
//并且为了防止重复筛选，也就是防止非最小质因子拆分，我们设计了if (k % Prime[j] == 0)break;这个条件主要是针对k为合数的筛选
//举个例子，若能整除，设倍数为n，则k=n*Prime[j],倘若我们在这里不break，那么下一个我们要标记的合数为i*Prime[j+1]=Prime[j]*n*Prime[j+1]
//即标记合数=Prime[j]*n*Prime[j+1],显然，当k=n*Prime[j+1]时，这个合数又会被筛一次，为了贯彻欧拉筛的分解最小质因数的筛法
//我们只取k为这个合数的最小质因数时的那一次筛，显然作为质因子来说，Prime[j]<Prime[j+1],所以我们决定在k=n*Prime[j+1]时来筛选这个合数
//这样的话这个合数的分解就会分解为最小质因子与k的乘积
//还是以12为例子。遍历时，当k=8，j=1时，Prime[j]=2,此时k%Prime[j]==0,若继续筛第j+1，Prime[j+1]=3，则此时的合数为8*3=24
// 但是显然，k=4*2(此时n=4),所以合数P=4*2*3，故当k=4*3时还会被筛一遍，对于两种情形，k=4*2，其质因子为3，对k=4*3，其质因子为2，显然取最小，故k=4*3时筛选
//由此，我们可以知道，欧拉筛对每个数只会筛掉一次，相较于埃氏筛对于12的多次重复筛（对i=2和i=3都会筛到12），时间复杂度有更一步的下降
//下面是实现
1 #include<stdio.h> 2 #include<stdbool.h> 3 #include<algorithm> 4 #include<stdlib.h> 5 #include<string.h> 6 #include<math.h>
//头文件插多了，别在意 7 #define MAXSIZE 1000 8 9 int* euler_sieve(int *cnt)//欧拉筛 10 { 11 int n; 12 scanf("%d", &n);//左边界 13 bool* IsPrime = (bool*)malloc(sizeof(bool) * (n + 1));//若i为素数，则IsPrime[i]=true,否则为false 14 memset(IsPrime, true, n + 1);//初始默认全为素数 15 IsPrime[0] = IsPrime[1] = false;//我们从2开始判断，对1和0这两个合数我们首先初始化为false 16 int* Prime = (int*)malloc(sizeof(int) * MAXSIZE);//用来存找到的素数 17 //准备工作结束 18 for (int k = 2; k <=n; k++)//开筛 19 { 20 if (IsPrime[k])//若是素数加入素数数组 21 Prime[(* cnt)++] = k; 22 for (int j = 0; j, j < *cnt && k * Prime[j] <= n; j++)//不论k是否是素数都会被用来筛选其最下质因数倍的合数 23 { 24 IsPrime[k * Prime[j]] = false;//合数标记 25 if (k % Prime[j] == 0)break;//重点 26 } 27 } 28 return Prime; 29 } 30 int main() 31 { 32 int cnt = 0;//素数个数统计 33 int *Prime=euler_sieve(&cnt); 34 for (int i = 0; i <cnt; i++) 35 { 36 printf("%d\n", Prime[i]); 37 } 38 return 0; 39 }