因子和相等的连续数

无心人 · 发表于 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不是个好的长度

能不能使用素数的连乘积长度？？

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

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