math - Project Euler #211 - 效率问题

Question

我一直在慢慢地解决欧拉项目问题的列表，我已经找到了一个我知道如何解决的问题，但似乎我不能(考虑到我的解决方案的编写方式)。

我正在使用 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))

使用更小、更友好的测试参数解决问题所需的时间似乎比指数增长还要大……这是一个真正的问题。

花了:

0.007 秒解决 100

0.107 秒解决 1000

2.020 秒解决 10000

56.61 秒解决 100000

1835.385 秒解决 1000000

24+小时解决64000000

我真的想弄清楚脚本的哪一部分导致它需要这么长时间。我已经考虑过记住因子函数，但我不知道如何实际实现它。

对于那些想看看问题本身的人， here it be .

任何关于如何使这件事变得更快的想法将不胜感激。

**对不起，如果这是对任何人的剧透，它并不意味着....

Answer 1

这是一个解决方案，牢记 [Project] Euler 的精神。 [警告:扰流板 .我试图保持提示缓慢，以便您可以仅阅读部分答案并根据需要自行思考。 :)]

当您遇到与数字有关的问题时，一个好的策略(您可能已经从解决 210 Project Euler 问题中了解到)是查看小例子，找到一个模式并证明它。 [根据你对数学的态度，最后一部分可能是可选的;-)]

但是，在这个问题中，查看小例子——对于 n=1,2,3,4,... 可能不会给你任何提示。但是在处理数论问题时，还有另一种“小例子”的含义，您现在可能也知道了——素数是自然数的组成部分，所以从素数开始。

对于素数 p，它的除数只有 1 和 p，所以它的除数的平方和是 1+p2。
对于素数 pk，它的除数只有 1, p, p2, ... pk，所以它的除数的平方和是 1+p+p2+...+pk=(pk+1-1)/(p-1 )。
那是最简单的情况:您只用一个质因数就解决了所有数字的问题。

到目前为止没有什么特别的。现在假设你有一个数 n，它有两个质因数，比如 n=pq。那么它的因数是1、p、q和pq，所以它的除数的平方和是1+p2+q2+p2q2=(1+p2)(1+q2)。
n=paqb 怎么样？它的因数的平方和是多少？

[…………阅读此行下方有危险……………………………………………………………………………………………………………………………………………… ....]

∑0≤c≤a，0≤d≤b(pcqd)2 = ((pa+1-1)/(p-1))((qb+1-1)/(q-1))。

这应该给你提示，关于答案是什么以及如何证明它:n 的除数之和只是其因式分解中每个素数的(答案)的乘积，所以你需要做的就是做的是分解 64000000(即使在一个人的头脑中也很容易做:-))并乘以每个(=两者，因为唯一的素数是 2 和 5)的素数幂的答案。

这解决了 Project Euler 问题；现在道德要从它那里拿走。

这里更普遍的事实是关于乘法函数——自然数上的函数使得 f(mn) = f(m)f(n) 每当 gcd(m,n)=1，即 m 和 n 在常见的。如果您有这样的函数，则该函数在特定数字处的值完全由其素数幂的值决定(您能证明这一点吗？)

稍微困难一点的事实，您可以尝试证明[这并不难]，是这样的:如果您有一个乘法函数 f [此处，f(n)=n2] 并且您将函数 F 定义为 F(n) = ∑d 除以 nf(d)，(正如这里的问题)，那么 F(n) 也是一个乘法函数。

【其实something very beautiful是真的，但现在不要看它，你可能永远不需要它。 :-)]