项目欧拉#211 - 效率问题

我一直在努力通过项目欧拉问题列表,我来到一个我知道如何解决,但似乎我不能(给我的解决方案写的方式).

我正在使用Common Lisp执行此操作,我的脚本已运行超过24小时(远远超过他们的一分钟目标).

为了简洁起见,这是我的解决方案(它是一个扰流板,但只有你有一个地狱的快速处理器):

(defun square? (num)
  (if (integerp (sqrt num)) T))

(defun factors (num)
  (let ((l '()))
    (do ((current 1 (1+ current)))
        ((> current (/ num current)))
      (if (= 0 (mod num current))
          (if (= current (/ num current))
              (setf l (append l (list current)))
              (setf l (append l (list current (/ num current)))))))
    (sort l #'< )))

(defun o_2 (n)
  (reduce #'+ (mapcar (lambda (x) (* x x)) (factors n))))

(defun sum-divisor-squares (limit)
  (loop for i from 1 to limit when (square? (o_2 i)) summing i))

(defun euler-211 ()
 (sum-divisor-squares 64000000))

使用更小,更友好的测试参数解决问题所需的时间似乎比exponentialy更大......这是一个真正的问题.

花了:

0.007秒解决100

0.107秒解决1000

2.020秒解决10000

56.61秒解决100000

1835.385秒解决1000000

24小时以上解决64000000

我真的想弄清楚脚本的哪个部分导致它花了这么长时间.我已经考虑了记忆因子功能,但我不知道如何实际实现它.

对于那些想要了解问题本身的人来说,就是这样.

关于如何让这件事变得更快的任何想法都将非常感激.

**对不起,如果这对任何人来说都是一个扰流板,它并不意味着......但是如果你有足够的计算能力在相当长的时间内运行它,那么对你来说就更有力量了.

这是一个解决方案,牢记[Project] Euler的精神.[警告:剧透.我试图保持缓慢的提示,这样你只能阅读部分答案并根据自己的想法自己思考.:)]

当你面临与数字有关的问题时,一个好的策略(正如你可能从解决210项目Euler问题中已经知道的那样)就是看一些小例子,找到一个模式并证明它.[最后一部分可能是可选的,取决于你对数学的态度;-)]

但是,在这个问题中,看一些小例子 - 对于n = 1,2,3,4,......可能不会给你任何提示.但是在处理数论问题时还有另一种"小例子"的意义,你现在也可能知道这些问题 - 素数是自然数的构成块,所以从素数开始.

对于素数p,其唯一的除数是1和p,因此其除数的平方和为1 + p ².
对于素数p ^k,其唯一的除数是1,p,p ²,... p ^k,因此其除数的平方和为1 + p + p ² + ... + p ^k =(p ^{k + 1} - 1)/(p-1).
这是最简单的情况:你已经解决了只有一个素因子的所有数字的问题.

到目前为止没什么特别 现在假设你有一个数字n有两个素因子,比如n = pq.那么它的因子是1,p,q和pq,所以它的除数的平方和是1 + p ² + q ² + p ² q ² =(1 + p ²)(1 + q ²).
那么n = p ^a q ^b呢？它的因素的平方和是多少？

[............................危险阅读此行以下............... ...]

它是_{Σ0≤c≤a,0≤d≤b}(p ^c q ^d)² =((p ^{a + 1} -1)/(p-1))((q ^{b + 1} -1)/(q -1)).

这应该给你提示,无论是答案是什么以及如何证明它:n的除数之和仅仅是其因子分解中每个主要权力的(答案)的乘积,所以你需要的只是分解为64000000(即使在一个人的头脑中很容易做到:-))并将每个(=两者,因为唯一的素数是2和5)的主要权力的答案相乘.

这解决了Project Euler问题; 现在是道德剥夺它.

这里更一般的事实是关于乘法函数 - 自然数上的函数,使得当gcd(m,n)= 1时f(mn)= f(m)f(n),即m和n没有素因子共同.如果你有这样一个函数,那么特定数字的函数值完全取决于它在主要幂上的值(你能证明这一点吗？)

稍硬的事实,你可以尝试证明[这不是说硬],是这样的:如果你有一个乘法函数f [这里,F(N)= N ² ]和您定义的函数F为F(N) =Σd _除n f(d),(如此问题所做),则F(n)也是乘法函数.

[事实上,非常美丽的东西是真的,但不要看它,你可能永远不会需要它.:-)]