| |
通法是试除.
对于特殊的如
2^p-1 的数有高效一些的方法:
1,
先找出小的因数, 例如我们要试 223-1
能否被47整除, 先使23转为二进制10111, 设初值 1 ,
反复平方, 并移去指数的二进制的高位,
若刚移去的高位是1 , 将刚平方的数乘 2,
然后计算它除以47的余数:
|
平方
|
移去高位
|
乘
2
|
mod
4
|
|
|
|
|
|
|
1*1
= 1
|
1
0111
|
1*2
= 2
|
2
|
|
2*2
= 4
|
0
111
|
no
|
4
|
|
4*4
= 16
|
1
11
|
16*2
= 32
|
32
|
|
32*32
= 1024
|
1
1
|
1024*2
= 2048
|
27
|
|
27*27
= 729
|
1
|
729*2
= 1458
|
1
|
故
223 = 1 mod 47. 两边减1 223-1 = 0 mod 47.
就是说 223-1 有因 47.
麦森数有一个很好的性质,
2P-1 的任何一个因数有形式 2kp+1 且 q=1 or 7 mod 8
, 而2P-1有95%的因数在40000以下.
2,
先精选一个限度B1, 将所有小于B1的素数相乘得E, 算 x
= 3E*2*P, 检查GCD(x-1, 2P-1)
3,
Lucas-Lehmer 素数测试法:
L(1) = 4
L(n+1) = (2L(n) - 2) mod (p2 - 1)
当且仅当 L[p-1] = 0 时 2^p-1 是素数.
更多分解法
|
| |
求a、b的最大公约数GCD:
1.质因数分解法：
1, 对两数分别分解质因数；
2, 找出共有的因数, 其乘积即是它们的最大公约数.
2.辗转相除法：
1, 若 a>b 执行<2>, 否则交换 a,b 执行<2>.
2, a <- a mod b
3, 若a或b等于一, 则另一个数是它们的最大公约数.否则执行<1>.
求a、b的最小公倍数LCM:
最小公倍数=ab÷最大公约数
对于求n个数的最大公约数&最小公倍数,
需分别求出每两个数的最大公约数（最小公倍数）将结果作同样处理.
|