典型算法举例

1、典型算法举例：历史上有三大算法：1，求最大公约数的欧几里得辗转相除法；2，求素数的埃拉托塞尼筛法；3，求方根的开方算法。后面两种方法都可以用公式表达。一，求素数的埃拉托塞尼筛法公式。属于递归的。筛法与公式的关系：公元前250年同样是古希腊的数学家埃拉托塞尼提出一种筛法：（一）“要得到不大于某个自然数N的所有素数，只要在2-N中将不大于N的素数的倍数全部划去即可”。（二）将上面的内容等价转换：“如果N是合数，则它有一个因子d满足1<dN”。（基础数论13页，U杜德利着，上海科技出版社）。.（三）再将（二）的内容等价转换：“若自然数N不能被不大于(根号)N的任何素数整除，则N是一个素数”。见

2、（代数学辞典上海教育出版社1985年。屉部贞世朗编。259页）。（四）这句话的汉字可以等价转换成为用英文字母表达的公式：N=p1m1+a1=p2m2+a2=.=pkmk+ak 。(1)其中 p1，p2，.，pk表示顺序素数2，3，5，,。a0。即N不能是2m+0，3m+0，5m+0，.，pkm+0形。若N<P（k+1）的平方 注：后面的1，2，3，.，k，（k+1）是脚标，由于打印不出来，凡字母后面的数字或者i与k都是脚标 ，则N是一个素数。（五）可以把（1）等价转换成为用同余式组表示：Na1(modp1)， Na2(modp2)，.，Nak(modpk)。 (2)例如，29，29不能够

3、被根号29以下的任何素数2，3，5整除，29=2x14+1=3x9+2=5x5+4。 291(mod2)，292(mod3)， 294(mod5)。29小于7的平方49，所以29是一个素数。以后平方用“*”表示，即：=m*。由于（2）的模p1，p2，.，pk 两两互素，根据孙子定理(中国剩余定理）知，（2）在p1p2.pk范围内有唯一解。例如k=1时，N=2m+1，解得N=3，5，7。求得了（3，3*）区间的全部素数。k=2时，N=2m+1=3m+1，解得N=7，13，19； N=2m+1=3m+2，解得N=5，11，17，23。求得了（5，5*）区间的全部素数。k=3时,-| 5m+1-|-

4、 5m+2-| 5m+3,| 5m+4.|-|-|-|-|-|n=2m+1=3m+1= |-31-|-7, 37-|-13,43|-19-|n=2m+1=3m+2= |-11,41-|-17,47-|-23-|-29-|-求得了（7，7*）区间的全部素数。仿此下去，可以求得任意大的数以内的全部素数。二，求方根的开方方法公式;开方的反馈方法或者叫做自动调节开方。方法是迭代的。公式：X_(n+1)=X_n+【A/(X（k-1）)-X_n】1/k"_"表示下角标，“”表示上角标。例如，X2,表示x的平方；X_1表示第一个X。例如，A=5，k=3.即开3次方。公式：X(n+1）=X

5、n+（A/Xn2-Xn）1/35介于13至23之间（1的3次方=1，2的3次方=8）X_0可以取1.1，1.2，1.3，1.4，1.5，1.6，1.7，1.8，1.9，2.0都可以。例如我们取2.0.按照公式：第一步：X_1=2.0+5/(2.02)-2.01/3=1.7.。即5/2×2=1.25，1.25-2=-0.75，0.75×1/3=0.25，2-0.25=1.75，取2位数值,即1.7。第二步：X_2=1.7+5/(1.72)-1.71/3=1.71.。即5/1.7×1.7=1.73010，1.73-1.7=0.03，0.03×1/3=0.01

6、，1.7+0.01=1.71。取3位数，比前面多取一位数。第三步：X_3=1.71+5/(1.712)-1.711/3=1.709第四步：X_4=1.709+5/(1.7092)-1.7091/3=1.7099.这种方法可以自动调节，第一步与第三步取值偏大，但是计算出来以后输出值会自动转小；第二步，第四步输入值偏小，输出值自动转大。X_4=1.7099.当然也可以取1.1，1.2，1.3，。1.8，1.9中的任何一个。.a必须大于或等于零，即a为非负数开平方公式X（n + 1） = Xn + (A / Xn Xn)1 / 2.。（n，n+1与是下角标）例如，A=5：5介于2的平方至3的平方;之

7、间。我们取初始值2.1，2.2，2.3，2.4，2.5，2.6，2.7，2.8，2.9都可以，我们最好取 中间值2.5。第一步：2.5+（5/2.5-2.5)1/2=2.2；即5/2.5=2，2-2.5=-0.5，-0.5×1/2=-0.25，2.5+(-0.25)=2.25，取2位数2.2。第二步：2.2+(5/2.2-2.2)1/2=2.23；即5/2.2=2.27272，2.27272-2.2=-0.07272，-0.07272×1/2=-0.03636，2.2+0.03636=2.23。取3位数2.23。第三步：2.23+(5/2.23-2.23)1/2=2.236

8、。即5/2.23=2.2421525，,2.2421525-2.23=0.0121525，,0.0121525×1/2=0.00607，,2.23+0.006=2.236.，取4位数。每一步多取一位数。这个方法又叫反馈开方，即使你输入一个错误的数值，也没有关系，输出值会自动调节，接近准确值。例如A=200.200介如10的平方-20的平方之间。初始值可以取11，12，13，14，15，16，17，18，19。我们去15.15+（200/15-15)1/2=14。取19也一样得出14.。：19+（200/19-19)1/2=14.。14+(200/14-14)1/2=14.1。14.1+（200/14.1-14.1)1/2=14.14.中间值，即1.5。 1.5+（5/1.52;-1.5）1/3=1.7。顺便介绍开5次方公式：X(n+1)=Xn+(A/X4-Xn)1/5 . (n，n+1是下角标）例如：A=5;5介入1的5次方至2的5次方之间。2的5次方是32，5靠近1的5次方。初始值可以取1.1，1.2，1.3，1.4，1.5，1.6，