从素数定义到欧拉筛，一步搞定数论基础之素数

什么是素数想搞定数论基础那素数与欧拉筛是绕不开的第一道关本文从素数的本质定义出发逐步拆解到欧拉筛的核心逻辑看完就能掌握两种素数筛选方法尤其适合算法入门/刷题补基础的同学。什么是素数首先我们来了解一下什么是素数。在大于1的自然数里1. 素数质数 只能被1和它自己整除即因数只有两个1和自身2. 合数 除了1和自己还能被别的数整除因数至少3个那么我们怎么用编程思维来找出素数呢接下来我讲解几种方法方法1试除法判断n是不是素数我们可以用 j 枚举2到n-1里的所有数如果n% j 0则不是素数。#define _CRT_SECURE_NO_WARNINGS #includeiostream 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且 an​。因为 a×bn所以另一个因数 ban​。代入不等式ban​n​n​n​反证法如果 n 是合数它一定有一个因数落在 [2,n​] 这个区间里。如果在 [2,n​] 里一个因数都没找到那 n 就不可能是合数只能是素数。#define _CRT_SECURE_NO_WARNINGS #includeiostream #includecmath 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数组bbi表示i是否是素数默认全是素数我们通过上面的原理可以把素数的倍数标记为合数。剩下的就都是素数了vectorint findprime(int n)//找出2到n所有的素数 { vectorbool isPrime(n1,true); isPrime[0] false; isPrime[1] false; vectorint 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次效率远高于埃氏筛 vectorint findprime02(int n) { // 1. 创建布尔标记数组isPrime[i] true 表示数字i初始被认为是素数 // 数组大小为 n1覆盖 0 ~ n 所有数字 vectorbool isPrime(n 1, true); // 2. 0和1不是素数直接标记为false isPrime[0] false; isPrime[1] false; // 3. 定义容器存储最终筛选出的所有素数 vectorint Prime; // 4. 外层循环遍历 2 ~ n 的所有数⚠️ 原代码写sqrt(n)是错误的必须遍历到n for (int i 2; i n; i) { // 如果当前数i是素数未被标记为合数将其加入素数数组 if (isPrime[i]) { Prime.push_back(i); } // 5. 内层循环用当前数i × 已找到的素数标记合数 // 条件1j不超出素数数组的范围 // 条件2i*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; }无注释版方便记忆vectorint findprime02(int n)//找出2到n所有的素数 { vectorbool isPrime(n 1, true); isPrime[0] false; isPrime[1] false; vectorint 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_sourcecopy_webvd_source9074883e5dde847a74ac32918f33f7e9