这是我第十二题的解法，解法粗暴一点，很慢，我想问问有没有更快的解法
有个思路就最好，用什么语言无所谓
(defn solution-12 []
(let [tran-nums (fn [num]
(cons (filterv #(zero? (rem num %)) (range 1 num))
num))]
(loop [n 1
c (count (tran-nums n))]
(if (= c 500)
n
(recur (inc n)
(count (tran-nums (inc n))))))))
我去，题目看错了，要三角数
因式分解目前没有快速的解法。如果你能快速算出来，那RSA之类的加密算法你就能快速破解了。
至于 factor 的话，自己挑个过得去的吧。
也可以考虑在 naive factor 上加个 memorization。
被樓上带歪了，这题根本不是因式分解好么。
第一个有 500 以上个因数的自然数的的区間可以估算在
9699690-223092870
因为 2^8<500<2^9, 通过简单的数论可以得出一个数的因数个数不小于质因数的 power set，2^n 是 n-element set 的 subset 数。前 8 个质数的积 9699690=×/2 3 5 7 11 13 17 19, 前 9 个质数的积 223092870=×/2 3 5 7 11 13 17 19 23
所以只要找到大于 9699690 的最少 triangular number 作为 initial case 再依次加上 base 就可以了。至于
这样把所有因数算出来就多余了，完全可以实现成个 constant space 的算法
以及你这里有个 bug，多于 n 个因数通常比正好 n 个因数的数早出现，题目要求的是 over 而不是 exactly
这个函数可以进一步优化，num约数（非num本身）应小于num的开方。换句话说，要测试的约数n的平方要小于num。
编辑：
以上错误。。。没仔细审题，我的错。一看到有关质数和约数，想都没想就直接用了这个条件。
但是还是可以优化，约数n（非num本身）应小于num/2
再次编辑：
想了一下，那个条件其实还是能用的，见8楼
28 的因数有 1 2 4 7 14 28，注意这里没要求质因数，14 怎會小于 sqrt 28，別被帶偏了
我想了一下，那个条件其实还是能用的。
因为count乘以2就行。
24: 1 2 3 4 6 8 12 24
这算不算反例
sqrt 24 = 4.8
1 < 4.8
2 < 4.8
3 < 4.8
4 < 4.8
小于4.8的有4个约数，总数就是4×2 = 8
6 和 4，8 和 3，12 和 2，24 和 1 是一对。
那加上个完全平方数的 case 是 ×2+1 就行。
比如 1 3 5 9 15 25 45 75 225
对，开方会比较慢。
这个论证实际是歪打误着。
对于一个正整数 n，如果它因式分解为 n = p_1^k_1 * p_2^k_2 * … * p_m^k_m（p_i 是质数，k_i 是正整数）, 那么它的因数的个数 d(n) = (1 + k_1)(1 + k_2)…(1 + k_m). （这应该也是简单的数论）
其实 d(n) 不小于质因数的幂集的模是没有问题的。因为显然每个 k_i >= 1，那么 d(n) >= (1+1)(1+1)…(1+1) = 2^m。但是其他的步骤有问题：
(1) 通过单边的缩放，d(n) >= 2^m，你只能得到一个下限，不可能同时得到下限和上限。不过这里限定了「第一个 d(n) 不少于 500」，所以设这么一个上限，结果数字也在里面了，所以说歪打误着。显然 2^499 正好有 500 个因数，但它远大于这个上限了。
从做题角度考虑，这里也没必要弄一个上限。弄出一个下限，就可以从这个下限开始往上计算了。 Project Euler 题是会有答案的，所以一直往上算就可以了。
(2) 然而，这个下限也是错的。
2^8 < 500 这个缩放，把任何一个满足 n > 2^8 的 n 替换掉 500 也不会影响得到这个下限。然而，第一个 d(n) >= 256 的正整数 n 是 1081080 = 2^3 * 3^3 * 5 * 7 * 11 * 13；不过 n = 256 不满足 n > 2^8, 可能不太好，那么我们看 n = 257 的情况，第一个 d(n) >= 257 的正整数 n 是 1441440 = 2^5 * 3^2 * 5 * 7 * 11 * 13.
把 500 缩放到 256 放得比较厉害了，只要选择一个比较接近 256 的数字就会发现这个下界是有问题的。其实问题在于，d(n) 并不是递增的（算几个 d(n) 就能够看出）；于是即使你有 d(n) >= 256, 同时对于某个数 x, d(x) = 256，也不能得到 n >= x.
同时从上面 n = 256 和 n = 257 的例子也能看出来问题，与其多增加一个质因数给 (1 + k_1)(1 + k_2)…(1 + k_m) 这个式子添加一项，不如给前几个 k_i 增大。多一个质因子 19 可以给 d(n) 多一倍，但是多上两个 2 也是一样的效果；然而一个是 * 19，而一个是 * 4, 差距就拉开了。不管是 1081080 还是 1441440 都是这个思路：尽可能增加小的质因子出现的次数。
用 Haskell 写了个，即使用 GHC 默认优化参数用估算出来的下界和从 1 开始只差了 0.4 秒 (4.28 和 4.68)。开了 O2 是 579.14 millis，带来的提升微乎其微。大概是 Scheme 不够快題主覚得慢大概就是因为把大于 500 写成正好 500 的 bug，反正下面改成 == 500 我跑了 1min 还没出来。在 Project Euler 网站上验过结果。
module Main where
import Data.List (find)
main = print $ pair
where pair = find ((500 <) . fst) $ map (factors `pd` id) $ (triToStream . tri) initial
pd f g = \n -> (f n, g n)
-- smallest tri num larger than
tri :: Int -> Int
tri p = ceiling $ (sqrt (fromIntegral $ p * 8 + 1) - 1) / 2
triToStream :: Int -> [Int]
triToStream n = (a : aux a n)
where a = (n * (n + 1)) `div` 2
aux a n = (a + n + 1 : aux (a + n + 1) (n + 1))
factors :: Int -> Int
factors n = 2 * (aux mid 0) - if n `div` mid == mid then 1 else 0
where mid = ((floor . sqrt) (fromIntegral n))
aux 1 acc = acc + 1
aux a acc = aux (a - 1) (acc + if mod n a == 0 then 1 else 0)
initial :: Int
initial = 9699690
建议去官网注册个帳号把答案先算对了再问。其实官网每題解开后都有个论坛有人贴解法。
多谢指教
ps:这个haskell代码完全看不懂啊
(define (factors n)
(let* ([mid (floor (sqrt n))]
[half (let loop ((a mid)
(acc 1))
(if (= a 1)
acc
(loop (1- a) (+ acc (if (= (mod n a) 0)
1
0)))))])
(+ (* 2 half)
(if (= n (* mid mid))
1
0))))
(define (problem12 n)
(let loop ((x (/ (* (+ n 1) n) 2))
(n (1+ n)))
(if (< 500 (factors x))
x
(loop (+ x n) (1+ n)))))
> (time (problem12 1393))
(time (problem12 1393))
811 collections
1.646439303s elapsed cpu time, including 0.012281831s collecting
1.647140000s elapsed real time, including 0.013833000s collecting
6842787616 bytes allocated, including 6842210896 bytes reclaimed
题主的程序是 clojure 啊。不会有人看到 defn 还觉得是 scheme 吧？
这个题主之前是用 Chez 的。順帶在我印象里 JVM 都不算很快。
对楼主没啥印象😥 但 defn，方括号（以及里面）的用法，recur 都很明显是 clojure 了
Scheme 也用方括号。主要 loop … recur 和 Scheme 的 let loop 结构也差不多，下意识就写出来 Scheme 了
其实scheme和clojure我都能看懂 
,只是clojure写的顺手一点