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

mathe · 发表于 2008-3-26 14:24:48

上面方法对于最大素数比较大的时候比较有效，但是对于最大素数比较小的情况，应该避免这种方法。那时可能还不如直接将各个素数相乘。

无心人 · 发表于 2008-3-26 14:26:05

你觉得一个三因子合数
如果排除了10000以下的
他还存在多大的合数因子，其素因子在10000以上？？？？
是不是不会存在素因子大于10000以上的合数因子

mathe · 发表于 2008-3-26 14:27:46

原帖由 无心人 于 2008-3-26 14:26 发表
你觉得一个三因子合数
如果排除了10000以下的
他还存在多大的合数因子，其素因子在10000以上？？？？
是不是不会存在素因子大于10000以上的合数因子

不懂，是指素数因子？

无心人 · 发表于 2008-3-26 14:32:56

我的意思
对于三个素因子且小于等于$10^12$的数n
只要排除<10000素因子，剩下的因子一定是素数

mathe · 发表于 2008-3-26 14:34:21

但是通常我们应该不会逐个n去筛选吧。
我会采用将各个素数相乘的方法。

无心人 · 发表于 2008-3-26 15:14:45

逐个筛选也不会很慢吧

mathe · 发表于 2008-3-26 15:17:12

看计算范围要多大。能有更好的算法不是更加好吗？

无心人 · 发表于 2008-3-26 15:20:02

应该不慢吧

mathe · 发表于 2008-3-26 15:31:50

从前面分析我们知道，如果n符合要求，那么对于n的任何一个素因子p有
$n=p + u*p(p-1)$其中$u$是不小于2的整数。
而对于任何这样的n,需要至少有3个以上不同的素因子。
所以另外一种可选的方法是可以先采用筛选法淘汰部分数据
对于每个整数，给定一个计数器初试化为0，
然后对于每个奇素数p,
对于所有整数 p+u*p(p-1),计数器加1。最后计数器不小于3的整数才有可能是最终结果。
不知道这个筛选效率如何。

无心人 · 发表于 2008-3-26 21:37:51

反正直接筛应该比用素数乘积堆容易写程序
筛一旦因子数过小就淘汰
而且，普通数字更大的概率是存在素因子小于100
则，能更快的淘汰
是否能做这么个算法
1、设定一个范围
2、对该范围数做<100素因子测试
3、如果存在，则测试p-1|n-1
4、3通过的和无小因子的保存做进一步测试

账号		自动登录	找回密码
密码			欢迎注册

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