球拍编程.我哪里错了? [英] Racket Programming. Where am I going wrong?

问题描述

我想回答的问题:
13195 的质因数是 5、7、13 和 29.600851475143 的最大质因数是多少?

The question i'm trying to answer:
The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

我哪里出错了?我的素数?测试似乎是问题所在，但它在相对较小的数字上运行良好.然而素数?测试给出了较大数字的错误答案.有没有更简单的方法来解决这个问题?

Where am I going wrong? my prime? test seems to be the issue, but it works fine on relatively small numbers. However the prime? test gives a wrong answer with larger numbers. Is there an easier way to go about this?

    (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)))

推荐答案

写成某个伪代码，你的意图好像是

Writing in a certain pseudocode, your intent seems to be

 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 一样.

read it: for x drawn from range 2 to 775146, if isPrime x holds, if 600851475143 % x is 0, collect such x; return the largest. We also write the application (g x) without the parentheses here, as just g x.

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

Calculating a remainder is cheaper than testing for primality, so we'll swap the two operations:

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

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

This algorithm might work for the specific numbers involved, but unfortunately it is incorrect in general - say for 9000009, whose integer square root is 3000, it will return 101. But 9901 is the right answer (i.e. 9901 is the biggest prime divisor of 9000009, not 101).

让我们首先专注于寻找最小质因数，而不是:

Let's first focus on finding the smallest prime factor, instead:

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

为什么 ( ... ++ [n]) (++ 表示列表的串联)??因为如果 n 本身是质数，则根本找不到除数，第一个列表将返回空，[].在这种情况下，答案必须是 n 本身.但如果不是，那么答案是除数列表的第一个(即 head).当然，当我们找到它时，我们不需要继续寻找更多.一个就够了，如果最小的就是我们所需要的.

Why the ( ... ++ [n]) (++ meaning the concatenation of lists)?? Because if n itself is prime, no divisor will be found at all, and the first list will come back empty, []. In which case the answer must be n itself. But if not, then the answer is the first (i.e. head) of the divisors list. Of course when we find it, we don't need to continue searching for more. Just one is enough, if the smallest is all we need.

好的，尝试一下(在一个虚构的惰性伪代码解释器中)，我们得到 3 作为它的第一个因素:

OK, so trying it (at an imaginary lazy pseudocode interpreter), we get 3 as its first factor:

> pe3a 9000009
3

现在我们可以用我们的数字除以 3:

Now we can divide that 3 out of our number:

> div 9000009 3 
3000003

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

and continue with 3000003, instead of 9000009. That means we can stop at its square root, 1732, instead of at 3000 - a sizable gain in efficiency! Also, we don't need to start over from 2 - it was tested already - we can start from the last found factor:

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，然后数字再次除以找到的除数.

so we get a second 3 back, and the number is divided by the found divisor once again.

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

找到的下一个质因数是 101，现在要分解的数是 1000001/101 = 9901.我们再次从最后找到的因数 101 开始，因为所有较小的因数都已经试过了:

the next prime divisor found is 101, and the number to factorize now is 1000001 / 101 = 9901. Again we start from the last found divisor, 101, because all the smaller ones were already tried:

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

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

Interesting. isqrt(9901) == 99, the list [101 .. 99] is empty, and so the result was immediately produced. 9901 is the first factor of itself above 100, and in fact above 1, because all the previous numbers were already tried, in succession, and divided out of it. That means 9901 is a prime, no need to test it for primality.

事实上，这个算法找到的所有因子通过相同的推理保证是质数，所有对isPrime的调用都是多余的.

In fact, all factors found by this algorithm are guaranteed to be prime by construction by the same reasoning, and all the calls to isPrime were superfluous.

还要注意，这里执行除法(余数运算)的最大数字是 101 - 不是 3000.我们的新算法不仅是正确的，而且还有更多高效！

Do also take note that the biggest number for which the division (the remainder operation) was performed here, was 101 - not 3000. Not only our new algorithm is correct, it is also much more efficient!

现在你可以在Scheme中编码这个重复pe3b应用程序并除以最后找到的因子的算法.达到 1 时停止.

Now you can code in Scheme this algorithm of repeated pe3b application and dividing by the last found factor. Stop when 1 is reached.

因此，在相同的伪代码中，

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

pe3 n = fst . until ((== 1) . snd) divStep $ (2,n)  -- (1st,2nd) in a tuple

factorizing n = takeWhile ((> 1) . fst) . drop 1 . iterate divStep $ (2,n)

factors n = map fst . factorizing $ n

isPrime n = factors n == [n]      

将 . 和 $ 读作of".until pred step start 是一个函数重复应用的高阶模式，直到满足一个谓词( ((== 1) . snd) 表示结果的第二个分量等于 1).它通常用名为 let 的 Scheme 编码.

Read . and $ as "of". until pred step start is a higher-order pattern of repeated applications of a function, until a predicate is fulfilled ( ((== 1) . snd) means that the second component of a result equals 1). It is usually coded in Scheme with named let.

要查看整个计算历史，iterate step start 是另一种模式，它收集所有中间结果(以及我们不需要的起始值，所以我们删除它).为了仅查看因素本身，我们使用 map fst 获取每个结果的第一部分.一个数是素数，如果它是它自身的唯一一个大于 1 的除数.测试:

To see the whole history of computation, iterate step start is another pattern which collects all the interim results (and the starting value, which we don't need, so we drop it). To see just the factors themselves, we take the first components of each result with map fst. A number is prime if it's the only divisor, greater than 1, of itself. Testing:

> pe3 9000009
9901
> factorizing 9000009
[(3,3000003),(3,1000001),(101,9901),(9901,1)]
> factors 9000009
[3,3,101,9901]

> pe3 600851475143
6857
> factorizing 600851475143
[(71,8462696833),(839,10086647),(1471,6857),(6857,1)]   -- 1471 is the largest
> factors 600851475143                                  --   factor tried, 
[71,839,1471,6857]                                      --   *not* 775146 !!

> factors 600851475143999917      -- isqrt 600851475143999917 == 775146099
[41,37309,392798360393]           -- isqrt 392798360393       ==    626736

这篇关于球拍编程.我哪里错了?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！