质数

## $$ \text{ 质数} $$ gyh实在是太⑨了,没脑子的他只能整理在这里: 如果以下内容中存在错误 ， 请及时通知博主 ， 博主会非常感谢您的指正 ， 并欢迎您把蠢货博主的头 **拧下来** 于 $2019.5.15$ 创建 于 $2019.5.16$ 修复了一些小 $bug$ 于 $2019.5.17$ 调整了 **费马小定理的证明** $$ \text{从此开始，一个天文单位} $$ $$ \large\downarrow $$　　　　　　　　 ------------ ### 定义： 如果一个数 ， 除了 $1$ 与**它本身** 外 ， 无其他因子 ， 这个数就被称为 **质数** ，否则被称为 **合数** 。 - 质数分布定理 ： 对于正实数 $x$ ，定义 $π(x)$ 为不大于 $x$ 的质数的个数，则有： $ π(x) \approx \frac{x}{ln \ x}$ (知道就好) $\large ps:\ $ **1既不是质数也不是合数** 1. ### 质因数分解 **定义 :任意一个大于1的正整数都能被唯一分解为有限个质数的乘积，可写作 :** $N = P^{c1}_1\times P^{c2}_2 \times ...\times P^{cm}_m$ 例 : $24 = 2^3 \times 3^1 $ - ###### 唯一分解定理: 对于某一正整数 $n$ , 其质因数分解方式是唯一的。 - ###### 正整数除法： 将 被除数 与 除数 先进行质因数分解 ， 再将对应每个质数的指数相减。 **例:** $24\div 8$ $= (2^3\times3^1)\div(2^3)$ $=2^{3-3}\times3^{1-0}$ $=3$ **可得:** 若 $m\mid n$ , 则: $n\div m =p_1^{a1-b1}\times p_2^{a2-b2}\times ...$ 中， 满足$a1>=b1,a2>=b2,...$ 若要验证$n$是否可被$m$整除, 则可以比较$n$与$m$质因数分解后的各项指数 若满足$a1>=b1,a2>=b2,...$, 即可判定$m\mid n$ ------------ 2. ### 素数判定 : - 试除法 "试除"，顾名思义，就是不断地尝试能否整除。 要判断自然数 $x$ 是否质数，就不断尝试小于 $x$ 且大于 $1$ 的自然数， 只要有一个能整除 $x$，则 $x$ 是合数；否则，$x$ 是质数。 复杂度是 $O(n)$ **优化 :** 设 $d≥ \sqrt x $ 是 $x$ 的约数，那 $\frac{x}{d} ≤ \sqrt x$ 也是 $x$ 的约数， 也就是说，约数是成对出现的，除了完全平方数,完全平方数的根下完全平方数是单独出现的。 所以我们只需要枚举 $i=[\ 1,\sqrt x\ ]$ 判断即可。 **代码 ：** ```cpp bool judge(int n) { if(n==1) return 0; for(int i=2;i<=sqrt(n);i++) if(n%i==0) return 0; return 1; } ``` 3. ### 筛法求素数 - ###### 埃氏筛 最简单的筛法 ： 复杂度为 $O(n log^2n )$ 对于枚举的数，枚举它的倍数， 并且将其倍数标记为合数 非常简单，直接贴代码： ```cpp int vis[N]; for(int i=2;i<=n-1;i++) for(int j=2;j*i<=n;j++) vis[j*i]=1; ``` 从代码可以发现 ： 一个数 会被它的 **所有因子** 都筛一遍 比如 ： $12$ ，就会被 $2,3,4,6$都筛去一遍 这就造成了时间上的浪费 。 那么该如何改进呢 ，请继续往下看 。 。 。 - ###### 欧拉筛 (线性筛) 复杂度为 $O(n)$ 思想与 埃氏筛 基本相同 ， 都是将一个数的 倍数 标记为 合数 **但 :** 保证了每一个数只被它的 **最小质因子** 筛掉一次 对于枚举的数 $i$ ，如果它之前没有被标记为合数 ， 就标记它为质数 。 然后枚举它的 **质数倍** ，并将其倍数标记为 合数 并在 $i \ mod\ $第 $j$ 个质数 $= 0$ 时, 结束枚举 。 先贴上代码： ```cpp int num; int p[N]; bool vis[N]; void prime(int n) { for(int i=2;i<=n;i++) { if(!vis[i]) p[++num] = i; for(int j=1;j<=num;j++)//枚举质数 { if(i*p[j] > n) break;//保证乘出的数不越界 vis[i*p[j]]=1;//打标记 if(!i%p[j]) break;//重点 } } } ``` 关于这一行： ```cpp if(!i%p[j]) break;//重点 ``` **解释 :** 设 $c = $ 接下来枚举的$i*p[j+k]$ ; $(k \in Z)$ 因为 $c$ 为 $i$ 的倍数 ，有着与 $i$ 相同的因数。 如果 $i\ \%\ p[j]=0$ , 那么，$c$ 也有 $p[j]$ 这个因子。 但是 $p[j+k]>p[j]$, 如果 $c$ ，在下一层循环,被 $p[j+k]$ 筛去， 他就不是被它 **最小的质因子** 筛去 当$i'\times p[j]\ =c$ 时,$c$ 又会被 $p[j]$ 筛去一遍 这就造成了重复,时间浪费。 为了保证 $c$ 是被他 **最小的质因子** 筛去 所以此处 $break$ , 结束循环 , 令 $c$ 在枚举 $i'$时 , 被它 **最小的质因子** 筛去 ------------ 4. ### 费马小定理 : **如果 $p$ 是一个质数 , 有整数 $a$ , 且 $a \perp p$ ,则: $a^{p-1} \equiv 1 (\mod p)$** - **证明 :** 设集合 $N = \{1,2 ,... ,(p-1)\}$ , 集合 $M = \{a,2a ,... ,(p-1)a\}$ 因为 $a \perp p$ , **则:** $M$ 中任意的数，都与 $p$ 互质。 易证 ：$M$ 中的任意两数 , $\pmod p$下 都不同余 - 子证明: 假设有 $Sa ,Ra \in M$ , 且$Sa \equiv Ra \pmod p $ **则:** $(S-R)a \equiv 0 \pmod p$ **则:** $(S-R)a = np,(n \in Z)$ 即: $p\mid (S-R)a$ 因为 $Sa ,Ra \in M$ ， **则:** $(S-R)< p$ 且 $a\perp p$ , **则:** $p\mid (S-R)a$ 不成立， 故原等式不成立 , 反证失败 ， 故集合 $M$ 中的任意两数，$\pmod p$都不同余 **则:** $N = \{1,2 ,... ,(p-1)\}$ , 与: $M = \{a,2a ,... ,(p-1)a\}\pmod p$ 有映射相等关系 . **则:** $\prod\limits_{i \in N} i \equiv \prod\limits_{j \in M} j \ (mod\ p) $ **即:** $(p-1)! \ \times \ a^{p-1} \equiv (p-1)!\ (mod\ p)$ **则:** 可得$a^{p-1} \equiv 1 (\mod p)$ **原式得证。** - 与欧拉定理的关系 不知道欧拉定理可以来这里看看： [约数 - 核融合炉心 - 洛谷博客](https://www.luogu.org/blog/koishikoishi/yue-shuo) 当 $p$ 为质数时 , $\Phi (p)= p-1$ 此时欧拉定理可写为 : $a ^{\Phi(p)} ≡ 1 \ \pmod p$ $a ^{p-1} ≡ 1 \ \pmod p$ 即 费马小定理。 可以发现，费马小定理 为 欧拉定理中 $p$ 为质数时的情况。 - 例 : 求 $2^{100}\ \% 13$ 解 : $\ \ \ \ 2^{100} \ (\mod 13)$ $\equiv (2 ^{13-1})^ 8 \times 2^4\ (\mod 13)$ $\equiv 1^8 \times 2^4\ (\mod 13)$ **则 :** 原式 $\ =1 \times 3 = 3$ ; ------------ 5. ### 二次探测定理 : 若 $p$ 为质数 , 且 $x^2 \equiv 1(\mod p)$ , 那么 $x \equiv 1 (\mod p) $ 和 $x \equiv p-1(\mod p)$ 中的一个成立 - ###### 证明: **由于 :** $x^2 \equiv 1 (\mod p)$ **则 :** $x^2-1 \equiv 0 (\mod p)$ $(x+1)(x-1) \equiv 0(\mod p)$ **即 :** $p\mid (x+1)(x-1)$ 原式得证 。 ------------ ------------ 本文为 @灵乌路空 @Luckyblock 原创 转载请联系作者,并注明出处 ~~(虽然这么个小破文肯定不会有人转载的)~~