查找素数：算法之美 | Wukong's Blog

给定一个数字n, 打印出n以内的所有素数。素数的定义非常简单，对于一个整数，除1和它本身外，再没有其他因数了，这个数就是素数。就是说，只除以1或者本身时余数为0，除以其他数所得的余数均不为0。

最简单的方法

-- 返回一个整数的所有因数
factors :: Integral a => a -> [a]
factorsn=[ x | x <- [1..n], mod n x == 0]

> factors 24 -- out: [1,2,3,4,6,8,12,24]
-- 检验一个数是否为素数的函数，只需检验它的因数是否只有1和他自己
isPrime :: Integral a => a -> Bool
isPrime n = factors n == [1, n]

-- 生成素数列表
primes :: Integral a => a -> [a]
primes n = [x | x<- [1 .. n], isPrime x]

上面的方法效率很低，每次求因数的时候，要从1～n全都遍历一遍

思考一下，可以简化一些过程

1. 除去2以外，所有的素数都必须为奇树
2. 素数必须是大于等于2的整数
3. 对于一个整数N，若它有一个因数为p1，必有另外一个因子p2，使得N=p1*p1，并 并且p1与p2 一 分布在N的两端或p1 =p2 = 根号下N;
4. 因为比2大的素数必须是奇数，所以它一 也不会有偶因数.

所以，对2进行单独讨论，然后对于其他的数只需要用它去除以所有 3 ∼ 根号下n的所有奇 数，若余数全不为0，则这个数为素数。
这样，对于isPrime可以这样定义

isPrime' :: Integral a => a -> Bool
isPrime' 2 = True
isPrime' p = p > 1 && (all (\n -> p `mod` n/=0 ) $ takeWhile(\n -> n*n <= p)[3,5..])
-- 注： takeWhile (\n -> n*n <= p) [3,5..]) 求出了 3 ∼ √N 的所有奇数数组成的列表

除此之外还有一个方法叫做埃拉托斯特尼筛法。给 从2开始连续的一列数，2为素数。那 么，在2之后有2 为因数的数均不为素数，可以被筛 。下一个数为3，3之后的所有为3的倍数的数就全被筛 了，因为4为2的倍数，这在第一轮中已经被筛掉了，下一个是5，依次类推，假设列表是无穷的，那么按着这个方法可以遍历所有的素数。

在看书时，阅读到这一块，就感觉真棒👍。填鸭式学习没有这样的思考过程，入门式的编程是以解决问题为主，未曾再进行思考。所以，入门加深入，会发现原来这个问题原来有如此优雅的方法。

PS: 以上出自haskell函数式编程入门