P39 - 无限素数列表与区间素数

2026-09-07 00:00    #Haskell   #99题   #数论  

P39 - 无限素数列表与区间素数

Construct prime numbers in a range & infinite list of primes

官方模块：Problems.P39　核心函数：primes、primesR

← P38 高欧拉函数数 | P40 哥德巴赫猜想 →

题目描述

构造所有素数组成的无限列表，并据此返回闭区间 [lo, hi] 内的素数。

函数签名

1primes  :: Integral a => [a]
2primesR :: Integral a => a -> a -> [a]

实现

方法一：试除已知素数（自引用）

1primes :: Integral a => [a]
2primes = 2 : filter primeWithKnown [3,5..]
3  where
4    primeWithKnown n =
5      all (\p -> n `mod` p /= 0)
6          (takeWhile (\p -> p * p <= n) primes)
7
8primesR :: Integral a => a -> a -> [a]
9primesR lo hi = takeWhile (<= hi) (dropWhile (< lo) primes)

判断候选数时，只试除已经生成且不超过平方根的素数。Haskell 的惰性求值允许 primes 引用自身较早的部分。takeWhile 保证判断 nn 时只需求值到 n\sqrt n 附近，循环定义不会失控。

方法二：埃拉托色尼筛法

1primes :: Integral a => [a]
2primes = 2 : sieve [3,5..]
3  where
4    sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

经典的"筛子"实现：每找到一个新素数，就从候选列表中过滤掉它的倍数。代码极简，但实际效率不如方法一（因为重复遍历和列表构建的开销大）。

方法三：区间筛（分段筛）

1primesR :: Integral a => a -> a -> [a]
2primesR lo hi
3  | lo > hi   = []
4  | otherwise = [x | x <- [lo..hi], isPrime x]

不依赖无限 primes 列表，直接对区间 [lo, hi] 用 P31 的 isPrime 逐个判断。对于小区间（如 primesR 1000000 1000100）足够快。

方法对比

方法惰性特点
试除已知素数✅标准做法，推荐
埃筛✅代码最简洁，教学经典
区间 isPrime✅不依赖 primes，适合小区间

测试

1>>> take 8 primes
2[2,3,5,7,11,13,17,19]
3>>> primesR 10 20
4[11,13,17,19]
5>>> primesR 20 10
6[]

参考