计算机算法基础-质数相关(持续更新)
计算机算法基础-质数相关(持续更新)
质数（素数）是大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。互质（互素）则是指两个或两个以上的整数的最大公因数为1。本文将详细介绍质数和互质数的基本概念、性质以及判断质数的方法。
质数（素数）定义
质数（素数）是大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
前提1: 属于 大于1自然数即 0 与 1 都不是质数
前提2: 约数仅有 1 和 本身
互质（互素）定义
若有2个 或者 2个以上的整数的最大公因数为1, 则称他们为 互质
例如: 5 和 7 只有 一个公因数: 1, 因此5 与 7 互质
推论
对于正整数集: 1 与所有 正整数 互质
对于整数集: 1 和 -1 与所有的整数互质, 并且, 它们是 仅与 0 互质的整数
性质
性质1
若 整数 a 与 b 互质, 则存在 整数 x, y, 使得x ∗ a + y ∗ b = g c d ( a , b ) = 1 xa + yb = gcd(a,b)=1x∗a+y∗b=gcd(a,b)=1(贝祖公式)
性质2
若两个数互质，那么两个数一定没有相同的质因数
证明：
∵ a 与 b 互质 \because a与b互质∵a与b互质
∴ g c d ( a , b ) = 1 \therefore gcd(a,b) = 1∴gcd(a,b)=1（互质的定义）
若 a , b 具有相同的质因数 p 若 a,b 具有相同的质因数 p若a,b具有相同的质因数p
则根据算数基本定理：任何数都看见恶意写成有限素数（质数）的乘积。 e.g：15 = 3 ∗ 5 15 = 3 * 515=3∗5
a = p k ∗ p 1 k 1 ∗ p 2 k 2 ∗ . . . ∗ p n k n ( p , p 1 , p 2 . . . p n 为 a 的 n + 1 个质因数 ) a = p_{}^{k}*p_{1}^{k1}p_{2}^{k2}...*p_{n}^{kn}(p,p_{1},p_{2}...p_{n}为 a 的n+1个质因数)a=pk ∗p1k1 ∗p2k2 ∗...∗pnkn (p,p1 ,p2 ...pn 为a的n+1个质因数)
b = p t ∗ q 1 t 1 ∗ q 2 t 2 ∗ . . . ∗ q m t m ( p , q 1 , q 2 . . . q m 为 b 的 m + 1 个质因数 ) b = p_{}^{t}*q_{1}^{t1}q_{2}^{t2}...*q_{m}^{tm}(p,q_{1},q_{2}...q_{m}为 b 的m+1个质因数)b=pt ∗q1t1 ∗q2t2 ∗...∗qmtm (p,q1 ,q2 ...qm 为b的m+1个质因数)
而此时g c d ( a , b ) = p m i n ( k , t ) ≠ 1 gcd(a,b) = p^{min(k,t)} ≠ 1gcd(a,b)=pmin(k,t)=1（最大公因数的底数为p pp，幂取k , t k,tk,t的最小值>0 00）
与互质的定义矛盾， 因此两个数互质的时候没有相同的质因数
证毕
判断是否是质数的方法
当一个数不是质数的时候, 一定存在 至少2个非1 非本身的约数
例如: 6, 6 /2 = 3, 两个非1非本身的约数 分别为: 2 和 3
这两个约数可能是相等的
例如: 4, 4/2 = 2, 分别为 2, 2;
设该数为: n, 则: n = √n * √n, 因此 对于 n = a*b,
较小的约数 <= √n <= 较大的约数,因此 我们判断一个数是否是质数的时候, 只需要判断[2, √n]是否有约数即可
任意偶数n一定可以分解为 n = 2 * x 的形式, 因此质数首先不可能是偶数, 其次, 质数也一定不会被其他偶数整除
**证明:对于质数 t, 偶数n, t / n = t / (2 * x) = (t / 2) * (1/x) ≠ 整数**
因而可知: 质数一定是奇数, 且不会被任意偶数整除, 即 约数只会是奇数,因此判断是否是质数的时候, 只需要判断[2, √t] 中的奇数即可