P31 - 判断素数
Determine whether an integer is prime
官方模块：
Problems.P31核心函数：isPrime
题目描述
素数是大于 1 且只有 1 和自身两个正因数的整数。判断给定整数是否为素数。
函数签名
1isPrime :: Integral a => a -> Bool
实现
方法一：试除枚举（2, 3, 5, 7, …）
1isPrime :: Integral a => a -> Bool
2isPrime 2 = True
3isPrime n
4 | n < 2 || even n = False
5 | otherwise = all (\d -> n `mod` d /= 0)
6 (takeWhile (\d -> d * d <= n) [3,5..])
若 是合数，则至少有一个因数不超过 。单独处理 2 和偶数后，只枚举奇数因数。
用 d * d <= n 避免转换成浮点数，也不会引入平方根舍入问题。
方法二：6k ± 1 优化（轮式试除）
1isPrime :: Integral a => a -> Bool
2isPrime n
3 | n < 2 = False
4 | n < 4 = True
5 | even n = False
6 | n `mod` 3 == 0 = False
7 | otherwise = all (\d -> n `mod` d /= 0 && n `mod` (d + 2) /= 0)
8 (takeWhile (\d -> d * d <= n) [5, 11..])
除了 2 和 3 之外，所有素数都具有 的形式。步长 6 比步长 2 减少 的检查量。
方法三：调用 P39 的素数列表
1isPrime :: Integral a => a -> Bool
2isPrime n
3 | n < 2 = False
4 | otherwise = n == head (dropWhile (< n) primes)
如果已经有了 P39 的无限素数列表，直接查表判断。但 dropWhile 需要生成所有小于 n 的素数，内存开销随 n 增长。
方法对比
| 方法 | 检查次数 | 特点 |
|---|---|---|
| 枚举奇数 | 约 √n/2 | 简单直接 |
| 6k ± 1 轮式 | 约 √n/3 | 常数优化 |
| 素数列表查表 | O(n/log n) 生成 | 复用已有列表 |
测试
1>>> isPrime 7
2True
3>>> isPrime 15
4False
5>>> map isPrime [-1,0,1,2,3,4]
6[False,False,False,True,True,False]