【分享】大质数判断及大因数分解。

awei

【素数检测方法】
对于任意个非2^n-1型奇数m,从1开始，作如下变换，如果遇到的数字是偶数，则除以2。如果遇到数字是奇数则加上m再除以2，直到结果为1，变换过程总共用了r步。假如有r能整除m-1,那么m为质数。
例1  m=7 。
(7+1)/2=4→4/2=2→2/2=1
即有 7→4→2→1
变换过程用了r=3 步，3|7-1，则7是质数。

例2  m=17 。
(17+1)/2=9→(9+17)/2=13→(13+17)/2=15→(15+17)/2=16→16/2=8→8/2=4→4/2=2→2/2=1
即有 17→9→13→15→16→8→4→2→1
变换过程用了r=8 步，8|17-1，则17是质数。

例3  m=23 。
(23+1)/2=12→12/2=6→6/2=3→(3+23)/2=13→(13+23)/2=18→18/2=9→(9+23)/2→16
  →16/2=8→8/2=4→4/2=2→2/2=1
即有 23→12→6→3→13→18→9→16→8→4→2→1
变换过程用了 r=11 步，11|23-1，则23是质数。

awei

【大因数分解方法】
对于任意个非2^n-1型奇数m,从1开始，作如下变换，如果遇到的数字是偶数，则除以2。如果遇到数字是奇数则加上m再除以2，直到结果为1，变换过程总共用了r步。假如有r能整除m-1,那么m为质数。不能整除则m为合数，用辗转相除法（欧几里得算法）求得r+1和m-1的最大公约数即可
例1 m=9 。
(9+1)/2=5→(5+9)/2=7→(7+9)/2=8→8/2=4→4/2=2→2/2=1
即有 5→7→8→4→2→1
变换过程用了r=5 步，辗转相除法求得（9,5+1）=3。

例3  m=21 。
(21+1)/2=11→(11+21)/2=16→16/2=8→8/2=4→4/2=2→2/2=1
即有 11→16→8→4→2→1
变换过程用了 r=5 步，辗转相除法求得（21,5+1）=3。

例3 m=25。
(25+1)/2=13→(13+25)/2=19→(19+25)/2=22→22/2=11→(11+25)/2=18→18/2=9→(9+25)/2=17→(17+25)/2=21→(21+25)/2=23→(23+25)=24
→24/2=12→12/2=6→6/2=3→(3+25)/2=14→14/2=7→(7+25)=16→16/2=8→8/2=4→4/2=2→2/2=1
即有 13→19→22→11→18→9→17→21→23→24→12→6→3→14→7→16→8→4→2→1
变换过程用了r=19 步，辗转相除法求得（25,19+1）=5。

awei

至于2^n-1型合数如何分解，当n为合数分解因数很简单（略去）。当n为质数，即2^n-1是梅森合数，暂时没有办法解决，但梅森数毕竟占的比例很少，走一里算一里吧