$\sum_{p<n}1/p=O(log(log(n)))$
n以内整数中，平均每个数的素因子的个数计算方法（重复的值计算一次），应该如mathe所言。
更明确的描述应该是这样的。 如n以内素数的个数为m,将第i个素数记为$P_i$ 则n以内的数总的素因子的个数为：
$n/P_1 + n/P_2+n/P_3 + ..n/P_m$
故平均每个数素因子的个数为 $1/P_1+1/P_2+...+1/P_m$
我们知道，当n很大是，n以内的自然数的倒数有极限，$\sum_{i=1}^{n}1/i=log(n)+C,c=0.5722$，但不知道mathe如何推出n以内的素数的倒数和公式。
那么筛法求素数的复杂度 就是 $n*log(log(n))$了?
我们知道对于一个整数x,它为素数的概率大概为$1/{log(x)}$,所以我们可以将
$sum_{p<n}1/p$近似写成$int_a^n1/{xlog(x)}dx=int_a^n{dlog(x)}/{log(x)}=int_{log(a)}^{log(n)}{dt}/t=O(log(log(n))$
小心这么晚睡觉
将来要长皱纹的
我想
把范围设为10^8吧
import Factoring
import Primes
readInt :: IO Integer
readInt = readLn
digitsSum n = if (n == 0) then 0 else ((n \`mod\` 10) + digitsSum (n \`div\` 10))
addFactors (a, b) = toInteger (b) * (digitsSum a)
isIn a l = any (==a) l
smithNumber n = [ n' | n' <- , not (isPrime n'), let nFactors = primePowerFactorsL n', (digitsSum n') == sum (map (addFactors) nFactors)]
smithNumber3 n =
smithNumber4 n =
main = do
putStrLn "Input Max n:"
n <- readInt
let filename = "ksmith" ++ show(n) ++ ".TXT"
writeFile filename (show \$ smithNumber3 n)
=========================================================
1000000内
可以看到，不存在4以上的
[ 本帖最后由 无心人 于 2008-11-25 11:12 编辑 ]
根据目前计算10^8的时间看
计算 10^12将花费的时间单位是天
即使用C语言写程序
似乎10 ^8花费时间将超过1小时
记录开始时间11:13
报个到先，看看我是否时间尝试一下。
100000000的尝试失败了
竟然4个小时没出结果
上面的代码在查找上是O(n^2)
经人指点优化下
import Factoring
import Primes
readInt :: IO Integer
readInt = readLn
digitsSum n = if (n == 0) then 0 else ((n\`mod\` 10) + digitsSum (n \`div\` 10))
addFactors (a, b) = toInteger (b) * (digitsSum a)
f (a, b, c) = (b == a+1) && (c == b+1)
smithNumber n = [ n' | n' <- , not (isPrime n'), let nFactors = primePowerFactorsL n', (digitsSum n') == sum (map (addFactors) nFactors)]
filter3 ls = filter f (zip3 ls (tail ls) (drop 2 ls))
smithNumber3 n = filter3 (smithNumber n)
main = do
putStrLn "Input Max n:"
n <- readInt
let filename = "ksmith" ++ show(n) ++ ".TXT"
writeFile filename (show \$ smithNumber3 n)