K-Smith numbers

mathe

$\sum_{p

liangbch

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))$了?

mathe

我们知道对于一个整数x,它为素数的概率大概为$1/{log(x)}$,所以我们可以将 $sum_{p

无心人

小心这么晚睡觉 将来要长皱纹的

无心人

我想 把范围设为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' <- [6..n], not (isPrime n'), let nFactors = primePowerFactorsL n', (digitsSum n') == sum (map (addFactors) nFactors)] smithNumber3 n = [n' | let smith = smithNumber n, n' <- smith, (isIn (n'+1) smith) && (isIn (n'+2) smith)] smithNumber4 n = [n' | let smith = smithNumber n, n' <- smith, (isIn (n'+1) smith) && (isIn (n'+2) smith) && (isIn (n'+3) smith)] main = do putStrLn "Input Max n:" n <- readInt let filename = "ksmith" ++ show(n) ++ ".TXT" writeFile filename (show \$ smithNumber3 n) ========================================================= 1000000内 [73615,209065,225951,283745,305455,342879,656743,683670,729066,747948,774858,879221,954590] 可以看到，不存在4以上的 [ 本帖最后由 无心人 于 2008-11-25 11:12 编辑 ]

无心人

根据目前计算10^8的时间看 计算 10^12将花费的时间单位是天 即使用C语言写程序 似乎10 ^8花费时间将超过1小时 记录开始时间11:13

liangbch

报个到先，看看我是否时间尝试一下。

无心人

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' <- [6..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)