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

mathe

直接筛选的确可以设计出一个不错的算法，不过感觉计算到M=10^12还是比较花费时间。应该比筛选素数的代码还要慢一些。
首先我们计算出所有不超过707107的素数(也就是(2p-1)p<10^12)
然后对于每个素数p,做如下筛选:
i)删除p,p^2,p^3,... (也就是删除所有p的整数幂)
ii)

1. for(i=2*p,t=2;i<M;i+=p,t++){
   
2.               if(t==p){///这里说明i=1(mod p-1)
   
3.                     t=1;
   
4.               }else{///这里说明i!=1(mod p-1)
   
5.                    删除候选数 i；
   
6.              }
   
7.      }

复制代码

通过上面筛选，余下就是卡米切尔数了。（当然所有偶数可以事先删除）

medie2005

我的浅见：

medie2005

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

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

无心人

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

mathe

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

无心人

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

mathe

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

mathe

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

无心人

结果太多

这种数很稀少的