Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

解答

这道题目很简单，就是要我们找出 600,851,475,143 的最大素因数。来看看我们的 Haskell 程序吧：

factors 1 = []
factors n = let p = head [ x | x <- [2..], mod n x == 0 ] in p : factors (div n p)
main = print $ last $ factors 600851475143

上述程序中：

• factors 函数返回其自变量的所有（从小到大排列的）素因数的列表。

• 第 1 行处理边界情况，整数 1 没有素因数，返回一个空列表。

• 第 2 行处理大于 1 的整数 n，从 2 开始逐个测试，遇到第一个能够整除 n 的数（这个数一定是素数）就停止，然后递归调用自身处理 n/p 。

• 第 3 行的 main 函数输出 600,851,475,143 的素因数列表的最后一个元素，就是我们要的答案。

改进

每次都从 2 开始逐个测试是没有必要的，完全可以从上次结束的地方开始测试：

factors = flip fact 2
fact 1 _ = []
fact n k = let p = head [ x | x <- [k..], mod n x == 0 ] in p : fact (div n p) p
main = print $ last $ factors 600851475143

上述程序中：

• 第 2 行至第 3 行的 fact 函数要求两个自变量，第一个是待分解的整数，第二个是测试的起始位置。递归调用自身时从刚刚分解出来的素因数开始。
• 第 1 行的 factors 函数简单地调用 fact 函数（将其第二个自变量置为 2）。flip 函数用于对调 fact 函数的两个自变量。当然，第 1 行改为 factors n = fact n 2 也是可以的。

再次改进

由于 2 是唯一的偶素数，因此我们可以先分解出所有的素因数 2，然后就可以只测试奇数了：

factors n = if even n then 2 : factors (div n 2) else fact n 3
fact 1 _ = []
fact n k = let p = head [ x | x <- [k,k+2..], mod n x == 0 ] in p : fact (div n p) p
main = print $ last $ factors 600851475143

上述程序中：

• 第 1 行的 factors 函数判断其自变量 n 是否为偶数，如是，则不断递归调用自身，分解出所有的素因数 2。如果 n 为奇数，则调用 fact 函数处理，注意这次测试的起始位置是 3 。

• 第 2 行至第 3 行的 fact 函数和前一个程序基本相同，除了只测试奇数以外。

最终的改进

由于整数 n 最多只能有一个素因数大于 ，我们可以相应设置测试的上限：

factors n = if even n then 2 : factors (div n 2) else fact n 3
fact 1 _ = []
fact n k = if null xs then [n] else let p = head xs in p : fact (div n p) p
  where xs = [ x | x <- [k,k+2..ceiling $ sqrt $ fromIntegral n], mod n x == 0 ]
main = print $ last $ factors 600851475143

上述程序中：

• 第 4 行通过 ceiling $ sqrt $ fromIntegral n 将列表的上限设置为 ，注意此时列表可能为空，表示要测试的数已经超过  了。

• 第 3 行要判断列表是否为空，如是，则此时 n 一定是素数，直接将 n 放入素因数列表中返回即可。

• 程序的其余部分和上一个程序相同。

注意，前面几个程序要测试的数的列表虽然是无限列表，但实际上等效于上限为 n 的列表。因为列表推导式中的条件 mod n x == 0，当 x 增加到 n 时一定会成立（虽然 x 可能没有增加到 n 程序就终止了，但 x 一定不会超过 n）。

详细的论述请参见：003_overview.pdf 。这些程序对小整数来说都足够快了，但是对大整数则太慢了。

 

 

*进阶

将大整数分解为素因数的乘积是一项非常困难的工作，目前最有效的方法是数域筛法，可参阅《整数分解》一书。

将下面这个整数分解为素因数的乘积，就可获得 20 万美元的奖金。Möchte jemand es probieren?

RSA-2048

RSA-2048 has 617 decimal digits (2,048 bits). It is the largest of the RSA numbers and carried the largest cash prize for its factorization, US$200,000. The largest factored RSA number is 768 bits long (232 decimal digits), and the RSA-2048 may not be factorizable for many years to come, unless considerable advances are made in integer factorization or computational power in the near future.