素数相关（结合回文数，合数）线性筛素数（欧拉筛法）Euler【算法模板笔记】
一、朴素筛法（埃拉托斯特尼筛法）
Eratosthenes 筛法（埃拉托斯特尼筛法，简称埃氏筛法）
时间复杂度是O(nloglogn)
不常用，被欧拉筛代替，略
二、线性筛素数（欧拉筛法）
简介
线性筛法 也称为 Euler 筛法（欧拉筛法）
对比
普通的筛法就是1到n的倍数来筛，线性筛就是 用1到n中的素数的倍数来筛
时间复杂度 O(n)
buff
筛法求素数的同时也得到了每个数的最小质因子。
原理
中心思想：每个数只能被自己的最小质因子筛掉一次
算法原理解释
原理：对于任意合数，必定可以有最小质因子乘以最大因子的分解方式。因此，对于每个合数，只要用最大因子筛一遍，枚举时只要枚举最小质因子即可。由于每个合数都只被标记一次，达到了线性
// 任意合数，必定可以有最小质因子乘以最大因子的分解方式。
// 所以我们只要保证每个合数都由最小质因子筛掉就行了
//用两层循环枚举最小质因子和最大因子。i是最大因子，prime[j]是最小质因子
break整除中断原因
解释1
// 这里为什么要break
// 因为如果不break
// i * p[j + 1] 的最小质因子就不是p[j + 1] 了
// 而是 i 的最小质因子 p[j]。
解释2
//这个break发生时，这个primes[j]的值，是i的最小质因子
//保证合数只被最小质因子划掉一次
//如果i是质数，则最多枚举到自身中断
//如果i是合数，则最多枚举到自身的最小质数中断
文章
【算法/数论】欧拉筛法详解：过程详述、正确性证明、复杂度证明_CSDN博客_欧拉筛
例题
P3383 【模板】线性筛素数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Sherlock and his girlfriend - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
三、与回文数结合
回文数
判断回文数
构造回文数
回文质数
偶数肯定不是质数。这样至少排除一半多的数据量
知识点： “偶数长度的回文数”中只有11是素数，其他的都可以被11整除。
偶数位数回文数（除11）必定不是质数
例题
回文素数 - 回文素数 - 力扣（LeetCode）
P1217 [USACO1.5]回文质数 Prime Palindromes - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
四、与合数结合
方法
用欧拉筛反向筛出合数
合数相关理论
例题
P1835 素数密度 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
模板
/*prime_nums_Euler*/
#include<bits/stdc++.h>
#define MAXN 100000005
using namespace std;//P3383 【模板】线性筛素数bool isprime[MAXN]; // isprime[i]表示i是不是素数
int prime[MAXN]; // 现在已经筛出的素数列表
int nums = 0; // 已经筛出的素数个数void euler_old(int n){memset(isprime, true, sizeof(isprime)); // 先全部标记为素数isprime[1] = false; // 1不是素数for(int i = 2; i <= n; ++i){ // i从2循环到n（外层循环）if(isprime[i]) prime[++nums] = i;// 如果i没有被前面的数筛掉，则i是素数for(int j = 1; j <= nums && prime[j] <= n/i; ++j){//枚举已经记录的质数（内层循环）//i * prime[j] <= n：由于题目只求小于n的数是否是质数，所以大于n的就不管了【越界中断】isprime[i * prime[j]] = false;// 倍数标记为合数，也就是i用prime[j]把i * prime[j]筛掉了if(i % prime[j] == 0) break;//【整除中断】}}
}//以下是acwing的模板int primes[MAXN], cnt; // primes[]存储所有素数
bool st[MAXN]; // st[x]存储x是否被筛掉:true表示要被筛掉（没有处理1的特判）void get_primes(int n){for(int i = 2; i <= n; i++){if(!st[i]) primes[cnt++] = i; //如果没有被筛掉，直接录入，并且cnt++for(int j = 0; primes[j] <= n/i; j++){ //从小到大枚举所有质数st[primes[j] * i] = 1; //筛掉质数的倍数的数if (i % primes[j] == 0) break; //【精髓：整除中断】//这个break发生时，这个primes[j]的值，是i的最小质因子}}
}int main(){int n; // 上限，即筛出<=n的素数scanf("%d", &n);get_primes(n);int q,k;//q次询问第 k 小的素数scanf("%d", &q);while(q--){scanf("%d", &k);printf("%d\n", primes[k-1]);}// for(int i = 2; i<=n; i++) if(isprime[i]) printf("%d ", i);// for(int i = 2; i<=n; i++) if(!st[i]) printf("%d ", i);return 0;
}