📄 16916.html
字号:
<html>
<head>
<title>缩小范围</title>
</head>
<body bgcolor="#FFFFFF" vlink="#808080">
<center>
<h1>缩小范围</h1>
</center>
<hr size=7 width=75%>
<hr size=7 width=75%><p>
Posted by <a href="mailto:honey0@tcts1.seed.net.tw">Honey</a> on August 09, 1999 at 09:46:29:<p>
In Reply to: <a href="16887.html">判断质数较快速的方法</a> posted by 早睡早起 on August 08, 1999 at 17:16:01:<p>
这可是很困难的数学问题<br>我想目前只能从几个定义和性质缩小寻找范围<br>目前我想到有三种方法<p>1.某个数K若有因数(也就是非质数)他必有因数介于1~(根号K)之间<br>搜寻范围可以不必到 K-1 要是1~根号K之间都不能整除 他必是质数<p>证明方法如下<p>假设K有1个正因数J,G存在,设J>=G,<br>J以及G必介于1~K之间且J*G=K.<br>则G的最大值为J(定义中J>=G)<br>故若存在因数G 他必介于大于1,小于等于J<br>当G=J时,又J*G=K.<br>即J*J=K<br>J=根号K<br>即 1 < G <= (根号K)<p>2.当个位数字是2,4,6,8,0他必是2的倍数(必定非质数 但2例外)<br> 当个位数字是5,0时他必是5的倍数(必定非质数 但5例外)<br>别以为这样没用 对于大体上而言<br>用2判断 对于所有的正因数是否为质数已经切掉了一半<br>加上5的判断 每100个连续整数变去掉60个<br>另外FOR~NEXT可定为STEP 2<br>更精细点 只要个位数字不为2,4,5,6,8,0<br>只要用个位数字是1,3,7,9的数去除就行了<br>如<br>11,13,17,19<br>21,23,27,29<br>31,33,37,39<br>41,43,47,49<p>以上这两个在最糟糕的情况下 会帮你省去9成以上的时间<p>例如(2^21701)-1 (这是质数) <br>这个数约等于4.486...*(10^6533)<br>只要搜寻1~21820...*(10^3267)次<br>少了99.999999....%(9有3000多位)<p>3.这个方法就有点困难了(9余数法)<br>对于相当大的数相当有帮助 我将例子稍稍讲出来<p>121=11*11<br>1+2+1=(1+1)*(1+1)<p>16*27=432<br>(1+6)*(2+7)=63<br>6+3 = 9 = 4+3+2<p>这可是有原理的喔 要的话我在证明出来给你看 因为有点烦 不打了<br>将某个述各位数字相加所得的值会等于某因数各位数字相加<br>后相乘的值 这样能推出所有可能的因数
<br>
<br><hr size=7 width=75%><p>
<a name="followups">Follow Ups:</a><br>
<ul><!--insert: 16916-->
</ul><!--end: 16916-->
<br><hr size=7 width=75%><p>
</body></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -