什么是素数
想搞定数论基础？那素数与欧拉筛是绕不开的第一道关！
本文从素数的本质定义出发，逐步拆解到欧拉筛的核心逻辑，看完就能掌握两种素数筛选方法，尤其适合算法入门/刷题补基础的同学。
什么是素数
首先，我们来了解一下什么是素数。
在大于1的自然数里：
1. 素数（质数） 只能被1和它自己整除，即因数只有两个：1和自身
2. 合数 除了1和自己，还能被别的数整除，因数至少3个
那么我们怎么用编程思维来找出素数呢？接下来我讲解几种方法
方法
1，试除法
判断n是不是素数，我们可以用 j 枚举2到n-1里的所有数，如果n% j ==0则不是素数。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> using namespace std; bool isprime01(int n) { if (n < 2)return false; if (n == 2)return true; for (int i = 2; i < n; i++) { if (n % i == 0)return false; } return true; }优化
我们只需要枚举到根号n即可，为什么呢？
📐 数学证明（严谨版）
假设 n 有一个因数 a，且 a>n。因为 a×b=n，所以另一个因数 b=an。代入不等式：b=an<nn=n
反证法：
如果 n 是合数，它一定有一个因数落在 [2,n] 这个区间里。如果在 [2,n] 里一个因数都没找到，那 n 就不可能是合数，只能是素数。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cmath> using namespace std; bool isprime01(int n) { if (n < 2)return false; if (n == 2)return true; for (int i = 2; i <=sqrt(n); i++) { if (n % i == 0)return false; } return true; }2，埃氏筛
原理：素数的倍数一定是合数。
所以，我们可以开一个bool数组b，b
i表示i是否是素数，默认全是素数，我们通过上面的原理可以把素数的倍数标记为合数。剩下的就都是素数了
vector<int> findprime(int n)//找出2到n所有的素数 { vector<bool> isPrime(n+1,true); isPrime[0] = false; isPrime[1] = false; vector<int> Prime; for (int i = 2; i <=sqrt(n); i++)//标记所有的合数， {//为什么小于等于sqrt(n),因为如果存在数x在sqrt(n)到n之间， //那么，他的一个因数一定在2到sqrt(n)之间。 if (isPrime[i]) { for (int j = i * i; j <= n; j += i)//标记所有的合数 { //为什么是i*i开始？ // 因为小于i*i的在前面已经被标记过了 isPrime[j] = false; } } } //筛出素数 for (int i = 0; i <= n; i++) { if (isPrime[i]) Prime.push_back(i); } return Prime; }但是我们发现，有很多数被重复判断。所以，再次优化
3，欧拉筛（线性筛）
原理：整数唯一分解定理
即。任何大于 1 的正整数，都能唯一分解为有限个质数的乘积
所以，我们在上面对素数的标记的方式上做了优化（非常NB）。
上面的方法是枚举素数，然后将素数的倍数标记为合数，下面，我们可以将素数存在一个数组里，然后，遍历的每一个数I都去乘素数，（也就是找素数的倍数）但是，这一次，当i取模素数表里的数等于0时，停止，进入下一个循环。
// 函数功能：欧拉筛（线性筛），找出 2 ~ n 之间的所有素数 // 时间复杂度 O(n)，每个合数仅被筛1次，效率远高于埃氏筛 vector<int> findprime02(int n) { // 1. 创建布尔标记数组：isPrime[i] = true 表示数字i初始被认为是素数 // 数组大小为 n+1，覆盖 0 ~ n 所有数字 vector<bool> isPrime(n + 1, true); // 2. 0和1不是素数，直接标记为false isPrime[0] = false; isPrime[1] = false; // 3. 定义容器，存储最终筛选出的所有素数 vector<int> Prime; // 4. 外层循环：遍历 2 ~ n 的所有数（⚠️ 原代码写sqrt(n)是错误的，必须遍历到n） for (int i = 2; i <= n; i++) { // 如果当前数i是素数（未被标记为合数），将其加入素数数组 if (isPrime[i]) { Prime.push_back(i); } // 5. 内层循环：用当前数i × 已找到的素数，标记合数 // 条件1：j不超出素数数组的范围 // 条件2：i*Prime[j] 不超过n，防止数组越界 for (int j = 0; j < Prime.size() && i * Prime[j] <= n; j++) { // 核心操作：标记合数 i*Prime[j] 为非素数 isPrime[i * Prime[j]] = false; // 6. 欧拉筛最核心优化：关键剪枝！ // 当i能被当前素数Prime[j]整除时，立即停止循环 // 原理：保证每个合数 只被它的「最小质因子」筛除一次，避免重复筛选 if (i % Prime[j] == 0) break; } } // 7. 返回存储所有素数的容器 return Prime; }无注释版，方便记忆
vector<int> findprime02(int n)//找出2到n所有的素数 { vector<bool> isPrime(n + 1, true); isPrime[0] = false; isPrime[1] = false; vector<int> Prime;//存储素数 for (int i = 2; i <= sqrt(n); i++)//标记所有的合数， { if (isPrime[i]) { Prime.push_back(i); } for (int j = 0; j < Prime.size()&&i*Prime[j]<=n; j++) { isPrime[i * Prime[j]] = false; //最重要的优化 if (i % Prime[j] == 0) break; } } return Prime; }更多详细讲解，可以去看看b站的这个视频。也是我学习的对象。
【找素数的3种方法 试除法 埃氏筛 线性筛 动画演示过程 noi大纲数论基础】 https://www.bilibili.com/video/BV11epre3E5K/?share_source=copy_web&vd_source=9074883e5dde847a74ac32918f33f7e9
){kind=spacer}
