P40 - 哥德巴赫猜想
Find two primes that sum to a given even integer
官方模块：
Problems.P40核心函数：goldbach
题目描述
哥德巴赫猜想认为每个大于 2 的偶数都能写成两个素数之和。给定这样的偶数，找出其中一组分解。
函数签名
1goldbach :: Integral a => a -> (a, a)
实现
方法一：基于 P39 的素数列表（推荐）
1goldbach :: Integral a => a -> (a, a)
2goldbach n
3 | n <= 2 || odd n = error "goldbach: even input greater than 2 required"
4 | otherwise = head
5 [(p, n - p) | p <- takeWhile (<= n `div` 2) primes
6 , isPrime (n - p)]
只枚举 可以避免把 (p,q) 与 (q,p) 重复考虑。复用 P31 和 P39。
方法二：基于 P31 的 isPrime（不依赖 primes）
1goldbach :: Integral a => a -> (a, a)
2goldbach n
3 | n <= 2 || odd n = error "goldbach: even input greater than 2 required"
4 | otherwise = head
5 [(p, n - p) | p <- [2..n `div` 2], isPrime p, isPrime (n - p)]
枚举 [2..n/2] 范围内所有整数，用 isPrime 检查。不依赖 P39 的无限素数列表，但对小数字枚举了更多候选（包括合数）。
方法三：从 n/2 向外搜索（平衡分解）
1goldbach :: Integral a => a -> (a, a)
2goldbach n
3 | n <= 2 || odd n = error "goldbach: even input greater than 2 required"
4 | otherwise = head
5 [(p, n - p) | offset <- [0..n `div` 2 - 2]
6 , let p = n `div` 2 - offset
7 , isPrime p, isPrime (n - p)]
从 开始向两侧搜索。这样找到的分解中两个素数最接近，常常得到最小的较大素数。
方法对比
| 方法 | 枚举范围 | 特点 |
|---|---|---|
| primes 列表 | 只检查素数 | 最少的试除次数 |
| 全枚举 | [2..n/2] | 不依赖 P39 |
| 从中间向外 | n/2 → 两侧 | 分解最平衡 |
测试
1>>> goldbach 12
2(5,7)
3>>> goldbach 28
4(5,23)
5>>> let (p,q) = goldbach 100 in p + q == 100 && isPrime p && isPrime q
6True
定义域
head 依赖哥德巴赫猜想在输入上成立。函数明确把定义域限制为大于 2 的偶数；它不是对任意整数都安全的查询接口。