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