快速计算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

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以内全部卡米切尔数