古代三大算法的公式

wxmwrk

    古代有三大算法：第一是寻找素数的埃拉特斯特尼筛法。
第二是求方根的开方法。
第三是欧几里得辗转相除法。


这些算法已经有两千多年，直到最近几年才找到公式。                                             

  第一，寻找素数的筛法公式
                                                                           素数的普遍公式

      要得到不大于某个自然数 n 的所有素数，只要在2— n 中将不大于素数的倍数全部划去即可。

      上述筛法可以总结为：

1，如果 n 是合数，则它有一个因子d 满足1 < d ≤。

2，若自然数n不能被不大于任何素数整除，则n是一个素数。（【代数学词典】259页，上海教育出版社）。

可以把2上面的汉字内容等价转换成为英语字母表示：

  .........(1)

其中 表示顺序素数2，3，5，....。≠0。

这样解得的 n，若 ,，则n是一个素数。


我们可以把（1）式内容等价转换同余式组表示 ：

  ........（2）

由于（2）的模,,..., 两两互素， 根据孙子定理(中国剩余定理）知，对于给定的,,...,，（2）式在...范围内有唯一解。 　

二，范例
例如， k=1时，，

解得n=3，5，7。求得了（3，））区间的全部素数。

k=2时，

，解得n=7，13，19；

  ，解得n=5，11，17，23。
求得了（5，）区间的全部素数。

k=3时
	31	7,37	13,43	19
	11,41	17,47	23	29

求得了（7,）区间的全部素数。

仿此下去可以求得任意大的数以内的全部素数。
并且一个不漏地求得。
对于所有可能的值，(1)和(2)式在...范围内，有（）（）()...（） 个解。
[url=][/url]
清华大学出版社【品数学】。




第二，求方根公式

         牛顿二项式定理在开方过程中可以与牛顿切线法等价，参见台湾中央研究院【数学传播】136期（从牛顿二项式定理开方到牛顿切线法）作者王晓明王蕊珂。

公式是迭代的。

                      .......(1)
=          .......（2）


举例：

一，开立方：　

.......(3)

例如，A=5，k=3,即求：

　5介于至之间（1的3次方=1，2的3次方=8）

初始值可以取1.1，1.2，1.3，1.4，1.5，1.6，1.7，1.8，1.9，2.0都可以。例如我们取按照公式：

第一步：=2+（5/-2)1/3=1.75。输入值大于输出值，负反馈；

即5/2×2=1.25，1.25-2=-0.75，-0.75×1/3=-0.25，2+(-0.25)=1.75，比前面多取一位数。即取2位数值,即1.7。

第二步：=1.7+（5/-1.7)1/3=1.71.输入值小于输出值，正反馈。

即5/1.7×1.7=1.73010，1.7301-1.7=0.03，0.03×1/3=0.01，1.7+0.01=1.71。取3位数，比前面多取一位数。

第三步：=1.71+（5/-1.71)1/3=1.709.

第四步：=1.709+（5/-1.709)1/3=1.7099

这种方法可以自动调节，第一步与第三步取值偏大，但是计算出来以后输出值会自动转小；第二步，第四步输入值

偏小，输出值自动转大。即5=

当然初始值也可以取1.1，1.2，1.3，。。。1.8，1.9中的任何一个,都是X_{1}=1.7

1.5+（5/-1.5）1/3=1.7。

二，开平方

如果用这个公式开平方，只需将(3)式的改成，1/3改成1/2。即

......(3)

例如，A=5：

5介于2²至3²之间。我们取初始值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.272727，2.272727-2.2=-0.072727，-0.072727×1/2=-0.036363，2.2+0.036363=2.23。取3位数。

第三步：2.23+(5/2.23-2.23)1/2=2.236。

即5/2.23=2.242,2.242-2.23=0.012,0.012×1/2=0.006,2.23+0.006=2.236.

每一步多取一位数。计算次数与计算精确度成为正比。这个方法又叫反馈开方，即使你输入一个错误的数值，也没有关系，输出值会自动调节，接近准确值。 这个方法的依据是根据牛顿切线法得来。也可以通过牛顿二项式定理推出。

第三，欧几里得辗转相除法

公式还没有找到。