水木社区手机版
- 主题:可能是最低效但却最神奇的素数计算法：用14个分数计算素数
- 有以下14个分数：
[upload=2][/upload]
试用n1=2去逐个试乘每个分数，直到得到整数乘积为止，此处找到的是第L个分数（15/2），乘积为15，记为n2；
然后再用n2重复以上步骤，此处找到的是N（55/1），乘积为825，记为n3；
依此类推，但要注意观察每个n(i)是否为2的整数次幂。在第19步，得到n(19) = 4 = 2^2，把幂记下来，为2；
再继续下去，第51步得到8 = 2^3，记下3；
然后经过213、430、1666步，分别得到32=2^5, 128=2^7, 2048=2^11……
我编了个程序来验算，一分钟能算到100附近的素数，之后的时间以指数速度增长——可以理解，我们找到就是指数啊。
请注意，在计算到17这个素数之前，常规的64位长整型就已经溢出了。之后的计算都需要使用专门编写的超长整数四则运算函数。效率确实低到令人发指，但神奇程度也不差，我到现在也没想通其原理是什么。
--
FROM 101.224.81.* - 【 在 prograft1 的大作中提到: 】
: 有以下14个分数：
: [upload=2][/upload]
: 试用n1=2去逐个试乘每个分数，直到得到整数乘积为止，此处找到的是第L个分数（15/2），乘积为15，记为n2；
: ...................
Conway发明的这种算法（注意它是可以直接编成程序的），他命名为Fractran。这个词是对Fortran (FORmula TRANslation）的play——还记得大学期间折腾过我们的这个老古董语言吗？
在这个框架下还可以编出其他的Fractran序列，例如，计算两个整数之和、之积差商，计算一个二进制数里有多少个“1”。它们有一个共同的特点——那就是低下得令人发指的效率
在用程序玩弄了几天Fractran之后，终于忍不住好奇心放狗搜索，在wiki上找到了其原理。读得半懂不懂。想研究一下的同学可以先不去找剧透。
--
FROM 101.224.81.*