球拍编程。我哪里错了？

Question

我试图回答的问题：
13195 的质因数是 5、7、13 和 29。数字 600851475143 的最大质因数是多少？

我哪里错了？我的盛年？test 似乎是问题所在，但它在相对较小的数字上工作得很好。但总理？测试给出了较大数字的错误答案。有没有更简单的方法来解决这个问题？

    (define b 3)

    (define z 0)

    (define divides?
      (lambda (a b)
        (= (remainder a b) 0)))

    (define (prime? n)
        (cond
          ((or (= n 1) (= n 0)) false)
          ((even? n) false)
          ((= n 2) true)
          ((= n b) true)
          ((divides? n b) false)
          (else (and (set! b (+ b 1)) (prime? n)))))

    ;Largest Prime Factor Test
    (define (LPF x)
      (cond
        ((divides? 600851475143 x)
         (cond
           ((prime? x)
            (cond
              ((> x z) (set! z x)))))))
      (if (< x 775146) (LPF (+ x 1)) (display z)))

Answer 1

用特定的伪代码编写，您的意图似乎是

 pe3 = last [x | x <- [2 .. 775146], isPrime x, rem 600851475143 x == 0]

读取：对于x从2到775146范围内抽取的，如果isPrime x成立，如果600851475143 % x为0，则收集这样的x；返回最大的. 我们在这里编写的应用程序也(g x)没有括号，就像g x.

计算余数比测试素性更便宜，因此我们将交换这两个操作：

pe3 n = last [x | x <- [2 .. isqrt n], rem n x == 0, isPrime x] 

该算法可能适用于所涉及的特定数字，但不幸的是，它通常是不正确的 - 例如对于 9000009，其整数平方根为 3000，它将返回 101。但9901是正确的答案（即 9901 是 9000009 的最大素因数） ，而不是 101）。

让我们首先关注寻找最小的质因数：

pe3a n = head ([x | x <- [2 .. isqrt n], rem n x == 0, isPrime x] ++ [n])

为什么( ... ++ [n])（++意思是列表的串联）？因为如果n它本身是素数，则根本找不到除数，并且第一个列表将返回空，[]。在这种情况下，答案必须是n它本身。但如果不是，那么答案就是head除数列表中的第一个（即 ）。当然当我们找到了之后，我们就不需要继续寻找更多了。如果我们只需要最小的，那么一个就足够了。

好的，所以尝试一下（在一个虚构的惰性伪代码解释器中），我们得到 3 作为它的第一个因子：

> pe3a 9000009
3

现在我们可以将这个数字除以 3：

> div 9000009 3 
3000003

并继续使用 3000003，而不是 9000009。这意味着我们可以停在其平方根 1732，而不是 3000 - 效率大幅提高！另外，我们不需要从 2 重新开始 - 它已经被测试过 - 我们可以从最后找到的因子开始：

pe3b (start, n) = (d, div n d)
  where
     d = head ([x | x <- [start .. isqrt n], rem n x == 0, isPrime x] ++ [n])

> pe3b (3, 3000003)
(3,1000001)

所以我们得到第二个 3，并且该数字再次除以找到的除数。

> pe3b (3, 1000001)
(101,9901)

找到的下一个素因数是 101，现在要分解的数字是 1000001 / 101 = 9901。我们再次从最后找到的除数 101 开始，因为所有较小的除数都已尝试过：

> pe3b (101, 9901)
(9901,1)

有趣的。isqrt(9901) == 99，列表[101 .. 99]是空的，所以结果立即产生。9901 是第一个高于 100 的因数，实际上高于 1，因为之前的所有数字都已被连续尝试并从中除掉。这意味着 9901 是素数，无需测试它的素数。

事实上，该算法找到的所有因子都可以通过相同的推理通过构造保证为素数，并且所有对 的调用isPrime都是多余的。

另请注意，此处执行除法（余数运算）的最大数字是 101 -而不是3000。我们的新算法不仅正确，而且效率更高！

pe3b现在您可以在Scheme 中编写重复应用并除以最后找到的因子的算法。当达到 1 时停止。

所以，在同一个伪代码中，

 pe3 = last [x | x <- [2 .. 775146], isPrime x, rem 600851475143 x == 0]

.and读$作“的”。until pred 步骤开始是重复应用函数的高阶模式，直到满足谓词（((== 1) . snd)意味着结果的第二个分量等于 1）。它通常用名为 的Scheme 进行编码let。

要查看计算的整个历史记录，iterate 步骤开始是另一种模式，它收集所有中间结果（以及起始值，我们不需要，所以我们需要drop它）。为了仅查看因素本身，我们将每个结果的第一个组成部分设为map fst。如果一个数是其自身唯一大于 1 的约数，则该数是素数。测试：

pe3 n = last [x | x <- [2 .. isqrt n], rem n x == 0, isPrime x]