估计是野蛮算法
暴力破解
应该存在些筛选条件
比如不能有大因子吧
的确是野蛮算法:)如果放到无心人的100多台机器，也许运行上一个月或者一年的，能够计算到$10^14$到$10^15$:lol
而在我自己的Linux上，我准备让它算到$10^11$,估计要花几个小时。
比如我们要搜索1~N中所有的目标数。
首先可以计算出1~$sqrt(N)$之间的所有素数。
事先开两个数组sums和prods都初始化为1
然后对于每个这个范围的素数p,我们对于p的所有倍数pk,计算出pk中含因子p的次数c
然后我们可以将prods乘上$p^c$,sums乘上$p^c+p^{c-1}+...+1$
最后我们再扫描一次prods数组，如果prods[ x ]里面的数据小于x,那么x/prods[ x ]肯定是一个素数,
这时候我们只要将prods再乘上这个素数加1就可以了。
当然实际计算过程中我们不可能保存整个sums和prods,需要分段计算。我是每1000000个数据一段
附件是代码,按惯例1枚金币:lol
原帖由 无心人 于 2008-4-30 13:59 发表 http://images.5d6d.net/dz60/common/back.gif
应该存在些筛选条件
比如不能有大因子吧
显然不能够是素数。
不过看前面几个结果都是素数的2倍，显然可以出现大因子
:)
厉害啊
发现前面计算的结果中
n和n+1都是$2^a*p$和$3^b*q$形式的数特别多(其中p,q是大素数)(2975不满足这个条件)
看来可以根据这个规律来搜索比较大的范围的解,不过这个结论我还没有分析原因
呵呵,我开始估计也是用经典筛法.不过你这个是分段筛.:)
特殊情况1:
$q=3^(b+1)-10$是素数
$p=(3^b*q+1)/2$是素数
那么我们可以找到一组特殊解:
$n=2p$
觉得1000000不是个好的长度
能不能使用素数的连乘积长度？？