欧拉筛法求素数

在开筛之前，我们要理解一个很好理解的概念，任何一个合数可以拆成一个最小素数和另一个数（可能质数可能合数）的乘积
这个最小素数即为这个合数的最小质因子
//比如 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 }