因子和相等的连续数

无心人 · 发表于 2008-4-30 13:51:15

估计是野蛮算法暴力破解

无心人 · 发表于 2008-4-30 13:59:37

应该存在些筛选条件比如不能有大因子吧

mathe · 发表于 2008-4-30 14:00:04

的确是野蛮算法

如果放到无心人的100多台机器，也许运行上一个月或者一年的，能够计算到$10^14$到$10^15$

而在我自己的Linux上，我准备让它算到$10^11$,估计要花几个小时。比如我们要搜索1~N中所有的目标数。首先可以计算出1~$sqrt(N)$之间的所有素数。事先开两个数组sums[N]和prods[N]都初始化为1 然后对于每个这个范围的素数p,我们对于p的所有倍数pk,计算出pk中含因子p的次数c 然后我们可以将prods[pk]乘上$p^c$,sums[pk]乘上$p^c+p^{c-1}+...+1$ 最后我们再扫描一次prods[N]数组，如果prods[ x ]里面的数据小于x,那么x/prods[ x ]肯定是一个素数, 这时候我们只要将prods[x]再乘上这个素数加1就可以了。当然实际计算过程中我们不可能保存整个sums[N]和prods[N],需要分段计算。我是每1000000个数据一段

mathe · 发表于 2008-4-30 14:02:18

附件是代码,按惯例1枚金币

mathe · 发表于 2008-4-30 14:04:10

原帖由 无心人 于 2008-4-30 13:59 发表应该存在些筛选条件比如不能有大因子吧

显然不能够是素数。不过看前面几个结果都是素数的2倍，显然可以出现大因子

无心人 · 发表于 2008-4-30 14:09:36

厉害啊

mathe · 发表于 2008-4-30 14:22:36

发现前面计算的结果中 n和n+1都是$2^a*p$和$3^b*q$形式的数特别多(其中p,q是大素数)(2975不满足这个条件) 看来可以根据这个规律来搜索比较大的范围的解,不过这个结论我还没有分析原因

medie2005 · 发表于 2008-4-30 14:23:30

呵呵,我开始估计也是用经典筛法.不过你这个是分段筛.

mathe · 发表于 2008-4-30 14:32:00

特殊情况1: $q=3^(b+1)-10$是素数 $p=(3^b*q+1)/2$是素数那么我们可以找到一组特殊解: $n=2p$

无心人 · 发表于 2008-4-30 14:32:20

觉得1000000不是个好的长度能不能使用素数的连乘积长度？？

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 因子和相等的连续数