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

mathe

上面过程如果输出需要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:25 上传

点击文件名下载附件

mathe

想到了个问题，主要在于素数筛选范围太小了些。没有考虑超大素数。还要淘汰所有大素数才行。
上面运行结果将>707107的素数全部留在里面了。

mathe

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

无心人

不用考虑超大素数啊
这类数去掉<=$root{3}{n}$小素数，剩下的因子准是素因子
小素数倍数足够了

按你程序时间还真不如筛好呢

mathe

速度慢是因为使用了大量内存，像搜索素数的程序一样，改成分段的筛选（就像求素数代码一样）应该会好很多。
简单筛选后还是需要对于余下的数分解因子，这个花费时间不会少。除非你筛选过程将因子直接保存下来了。
两外，对于更加大范围的数据，我觉得还是要采取将素数相乘的方法。

无心人

如果有快速算法能迅速淘汰不合适的数
则筛法可行
如果没有，可能你的对

无心人

要不这么来
3肯定不合适
从5开始，每个素数采取类似筛法求素数的方法，筛素数
遇到数，就检验p-1)|n-1
如果不行，就剔除
关键是如何最快速的跳过已剔除数

mathe

原帖由 medie2005 于 2008-3-27 10:26 发表
假设卡米切尔数n由d个奇素数组成，分别记为p(1),p(2),...,p(d).
1<=r<d．
记Pr=p(1)*p(2)*...*p(r)，Qr=p(r+1)*...*p(d)，Tr=LCM((p(1)-1)，(p(2)-1)，...，(p(d)-1))．
那么，有n=Pr*Qr=1 mod Tr
先搜索前r个素数，Pr和Tr也就可以确定，我们利用扩展的gcd算法，是否可以确定Qr？

加上约束条件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

无心人

以1000内素数为例
最多2个素数测试
可能的组合10000多
必须有排除部分组合的方法

medie2005

10^12以内全部卡米切尔数表.