# 缩小范围

Posted by Honey on August 09, 1999 at 09:46:29:

In Reply to: 判断质数较快速的方法 posted by 早睡早起 on August 08, 1999 at 17:16:01:

这可是很困难的数学问题
我想目前只能从几个定义和性质缩小寻找范围
目前我想到有三种方法

1.某个数K若有因数(也就是非质数)他必有因数介于1~(根号K)之间
搜寻范围可以不必到 K-1 要是1~根号K之间都不能整除 他必是质数

证明方法如下

假设K有1个正因数J,G存在,设J>=G,
J以及G必介于1~K之间且J*G=K.
则G的最大值为J(定义中J>=G)
故若存在因数G 他必介于大于1,小于等于J
当G=J时,又J*G=K.
即J*J=K
J=根号K
即 1 < G <= (根号K)

2.当个位数字是2,4,6,8,0他必是2的倍数(必定非质数 但2例外)
当个位数字是5,0时他必是5的倍数(必定非质数 但5例外)
别以为这样没用 对于大体上而言
用2判断 对于所有的正因数是否为质数已经切掉了一半
加上5的判断 每100个连续整数变去掉60个
另外FOR~NEXT可定为STEP 2
更精细点 只要个位数字不为2,4,5,6,8,0
只要用个位数字是1,3,7,9的数去除就行了
如
11,13,17,19
21,23,27,29
31,33,37,39
41,43,47,49

以上这两个在最糟糕的情况下 会帮你省去9成以上的时间

例如(2^21701)-1 (这是质数)
这个数约等于4.486...*(10^6533)
只要搜寻1~21820...*(10^3267)次
少了99.999999....%(9有3000多位)

3.这个方法就有点困难了(9余数法)
对于相当大的数相当有帮助 我将例子稍稍讲出来

121=11*11
1+2+1=(1+1)*(1+1)

16*27=432
(1+6)*(2+7)=63
6+3 = 9 = 4+3+2

这可是有原理的喔 要的话我在证明出来给你看 因为有点烦 不打了
将某个述各位数字相加所得的值会等于某因数各位数字相加
后相乘的值 这样能推出所有可能的因数

Follow Ups: