数学研发论坛

 找回密码
 欢迎注册
楼主: medie2005

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

[复制链接]
发表于 2008-4-30 13:51:15 | 显示全部楼层
估计是野蛮算法
暴力破解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-30 13:59:37 | 显示全部楼层
应该存在些筛选条件

比如不能有大因子吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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个数据一段
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-30 14:02:18 | 显示全部楼层
附件是代码,按惯例1枚金币

fx.tar.gz

59.68 KB, 下载次数: 2, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

售价: 1 枚金币  [记录]  [购买]

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-30 14:04:10 | 显示全部楼层
原帖由 无心人 于 2008-4-30 13:59 发表
应该存在些筛选条件

比如不能有大因子吧

显然不能够是素数。
不过看前面几个结果都是素数的2倍,显然可以出现大因子
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-30 14:09:36 | 显示全部楼层


厉害啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-30 14:22:36 | 显示全部楼层
发现前面计算的结果中
n和n+1都是$2^a*p$和$3^b*q$形式的数特别多(其中p,q是大素数)(2975不满足这个条件)
看来可以根据这个规律来搜索比较大的范围的解,不过这个结论我还没有分析原因
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-30 14:23:30 | 显示全部楼层
呵呵,我开始估计也是用经典筛法.不过你这个是分段筛.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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不是个好的长度

能不能使用素数的连乘积长度??
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-3-26 08:40 , Processed in 0.052546 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表