找回密码
 欢迎注册
楼主: 无心人

[讨论] 快速计算10^12以内全部卡米切尔数

[复制链接]
发表于 2008-3-27 14:25:32 | 显示全部楼层
上面过程如果输出需要49.6秒。 前面10个数据是 561 1105 1729 2821 6601 8911 10585 29341 41041 46657 附件是源代码。如果要支持到10^12,肯定还要做一些关于cache方面的优化以及汇编优化。不然这里至少还要运行1000倍左右的时间还是受不了的。 kmr.gz (950 Bytes, 下载次数: 8)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-27 14:29:00 | 显示全部楼层
想到了个问题,主要在于素数筛选范围太小了些。没有考虑超大素数。还要淘汰所有大素数才行。 上面运行结果将>707107的素数全部留在里面了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-27 14:30:51 | 显示全部楼层
2^19以内计算出来只有30个,应该没有问题,因为它们都小于707107,所以还需要在加一段代码,将大于707107的素数全部计算出来,直接将这些素数删除就可以了。 561 1105 1729 2821 6601 8911 10585 29341 41041 46657 52633 62745 63973 101101 115921 126217 162401 172081 188461 252601 278545 294409 314821 334153 340561 399001 410041 449065 488881 512461
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-27 17:28:05 | 显示全部楼层
不用考虑超大素数啊 这类数去掉<=$root{3}{n}$小素数,剩下的因子准是素因子 小素数倍数足够了 按你程序时间还真不如筛好呢
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-27 17:41:18 | 显示全部楼层
速度慢是因为使用了大量内存,像搜索素数的程序一样,改成分段的筛选(就像求素数代码一样)应该会好很多。 简单筛选后还是需要对于余下的数分解因子,这个花费时间不会少。除非你筛选过程将因子直接保存下来了。 两外,对于更加大范围的数据,我觉得还是要采取将素数相乘的方法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-27 17:45:27 | 显示全部楼层
如果有快速算法能迅速淘汰不合适的数 则筛法可行 如果没有,可能你的对
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-27 17:47:05 | 显示全部楼层
要不这么来 3肯定不合适 从5开始,每个素数采取类似筛法求素数的方法,筛素数 遇到数,就检验p-1)|n-1 如果不行,就剔除 关键是如何最快速的跳过已剔除数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-28 07:55:18 | 显示全部楼层
原帖由 medie2005 于 2008-3-27 10:26 发表 假设卡米切尔数n由d个奇素数组成,分别记为p(1),p(2),...,p(d). 1<=r
加上约束条件p(1)>p(2)>....>p(d) Tr(r)=LCM(p(1)-1,p(2)-1,...,p(r)-1) 那么给定Pr后 Q(r)=x+Tr(r)*u 其中x可以通过中国剩余定理算出,u为待定系数 实际计算过程可以选择r很小,但是Pr*Tr(r)不能小于一个给定的数M,假设搜索范围为N,那么可以估算出大概1<=u<=N/M. 通过这种方法应该可以找出更大范围的解,估算一下计算到10^12以内应该没有问题,也许可以算到更加大的范围,比如10^15
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-3-28 08:11:35 | 显示全部楼层
以1000内素数为例 最多2个素数测试 可能的组合10000多 必须有排除部分组合的方法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-3-28 09:40:38 | 显示全部楼层
推荐
10^12以内全部卡米切尔数表.

Carmichael Numbers.rar

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

10^12内的Carmichael Numbers

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-11-15 01:16 , Processed in 0.026759 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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