快速计算10^12以内全部卡米切尔数
数论研究--算法讨论--程序实现，占全了:)若整数n非素正整数且对所有正整数a 满足a^n-=a\quad(mod n)
则称n为卡米切尔数
现求一快速算法求出10^12内所有卡米切尔数
前三个数字是：561,1105,1729 没有人迎战么？
===============
至少要有人出来分析下啊 假设
$n=p_1^{u_1}p_2^{u_2}...p_k^{u_k}$
其中$p_1,p_2,...,p_k$为不同的素数
记
$m=LCM( (p_1-1)p_1^{u_1-1}, (p_2-1)p_2^{u_2-1},...,(p_k-1)p_k^{u_k-1})$
那么就是说
$m|n$
也就是要求
$p_1-1| n/{p_1^{u_1}}$
$p_2-1|n/{p_2^{u_2}}$
...
$p_k-1|n/{p_k^{u_k}}$ 错了，上面应该是要求
$m|n-1$
所以
$u_1=u_2=...=u_k=1$ 也就是
$n=p_1 p_2 ... p_k$
而且
$p_1 -1|n-1$
$p_2 -1|n-1$
...
$p_k-1|n-1$
使用这个结果计算$10^12$以内所有解应该已经不是问题了。 还有至少3个素数，n必须是奇数 还有对于每个素因子p,$p(2p-1)<=n$,由此我们只要$10^6$以内的素数表。是不是这说明我们还可以加大搜索范围 还有，至少有三个因子
因此只需要10000以下素数
有1000000的可搜索$10^18$的 想到一种比较可行的算法。
假设计算N以内的数
我们首先找到所有奇素数p使得p(2p-1)<=N，把这个列表记住L
然后对于每个这样的素数p,
M=;
for(x=(2*p-1);x<=M;x+=p-1){
检查x的每个素因子q,
如果q^2|x,那么淘汰x
如果(x*p-1)%(q-1)!=0,淘汰x
如果对于所有的x的素因子q,x都没有被淘汰，那么x*p就是就是一个解。
} 原帖由 无心人 于 2008-3-26 14:17 发表 http://images.5d6d.net/dz60/common/back.gif
还有，至少有三个因子
因此只需要10000以下素数
有1000000的可搜索$10^18$的
你这是以最小的素因子为基准，我是以最大的素因子为基准