论坛 › 算法交流 › 快速计算10^12以内全部卡米切尔数

mathe 发表于 2008-3-27 10:00:38

直接筛选的确可以设计出一个不错的算法，不过感觉计算到M=10^12还是比较花费时间。应该比筛选素数的代码还要慢一些。
首先我们计算出所有不超过707107的素数(也就是(2p-1)p<10^12)
然后对于每个素数p,做如下筛选:
i)删除p,p^2,p^3,... (也就是删除所有p的整数幂)
ii)for(i=2*p,t=2;i<M;i+=p,t++){
            if(t==p){///这里说明i=1(mod p-1)
                  t=1;
            }else{///这里说明i!=1(mod p-1)
                   删除候选数 i；
             }
   }通过上面筛选，余下就是卡米切尔数了。（当然所有偶数可以事先删除）

medie2005 发表于 2008-3-27 10:16:50

我的浅见：

medie2005 发表于 2008-3-27 10:26:51

假设卡米切尔数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？

medie2005 发表于 2008-3-27 10:49:01

应是：Tr=LCM((p(1)-1)，(p(2)-1)，...，(p(d)-1))．

无心人 发表于 2008-3-27 11:46:01

mathe啊
通过那些筛选只是候选而已啊

mathe 发表于 2008-3-27 12:58:41

我那个筛法留下来不仅仅是候选数。

无心人 发表于 2008-3-27 13:41:56

那就筛下<10000看剩下的是不是？

mathe 发表于 2008-3-27 14:17:27

运行了一下，的确有些错误，第一步改成筛所有p^2的倍数就可以了。原先以为可以省略的。

mathe 发表于 2008-3-27 14:19:27

运行了一下
2^30以前应该有75541546个，如果仅仅统计不输出需要花费32.6秒。

无心人 发表于 2008-3-27 14:23:41

结果太多

这种数很稀少的

查看完整版本: 快速计算10^12以内全部卡米切尔数