（笔者是Haskell初学者。为了更好掌握Haskell和函数式思维方式,特地去欧拉计划（Project Euler）上刷算法题。本文是针对第10题的心得。文中难免有错误之处，欢迎各路大牛留言指正。）
欧拉计划 第10题 求素数（质数）之和
10以下的质数的和是2 + 3 + 5 + 7 = 17.
找出两百万以下所有质数的和。
访问地址
常规思路
素数（质数）是除了1和它本身以外，不再被其他数整除的数。目前求素数最常见的方法，就是筛选法：从2开始、某一范围内的正整数从小到大顺序排列。其中选择最小的数就是素数，然后去掉它的倍数。依次类推，直到全部筛选完成。
废话少说，直接上代码（伪代码）：
该算法已做了优化。至于为何这样优化，那属于算法专家或数学家的范畴了，恕笔者就不班门弄斧了。有兴趣的读者，可以自行研究。（文中算法来自 Sieve of Eratosthenes - Wikipedia）
函数式编程思路
因为函数式编程中没有循环的概念。所以上面的伪代码是无法照搬的。不过，函数式编程中有递归的，所以我们用递归来解决本问题。下面是递归解决流程：
//递归流程（以10为例）：
f([2,3,4,5,6,7,8,10]) = 2 ++ f([3,5,7,9])
f([3,5,7,9]) = 3 ++ f([5,7])
f([5,7]) = 5 ++ f([7])
f([7]) = 7 ++ f([])
f([]) = []
//结果[2,3,5,7]
函数f的参数是数字List，然后取出第一个元素，并用这个元素对剩下的元素进行筛选，筛选完的数据list，递归调用本函数。
用Haskell表示上述函数：
findPrime [] = []
findPrime (x:xs) = x : findPrime (filter (\a -> not $ a `mod` x == 0) xs)
这里是递归调用函数findPrime。筛选过程采用filter过滤，筛选的逻辑使用Lambda表达式，以参数方式传给filter。Lambda表达式是\a -> not $ amodx == 0,表示把不能被整除的数留下（返回True）。（注：这里未使用优化）
执行结果：
从结果可见：该函数的参数是List，返回也是List。
算法优化
当前，这个findPrime函数没有使用前面算法中的优化，所以执行200万的数据时，就会非常非常慢。
所以按前面的算法进行优化：
findPrime [] = []
findPrime all@(x:xs) = if (x > floor (sqrt 200*10000)) then all else x : findPrime (filter (\a -> not $ (a - x*x) `mod` x == 0) xs)
优化的的步骤很简单：
- 增加了if，即如果list的第一个元素大于200万的开方值时，停止递归；
- 筛选过程（Lambda表达式）使用优化算法，即按（i平方+n*i)方式进行刷选。
执行时间在可承受范围（便于显示，笔者对结果list又进行了sum求和）：
总结：
在上文中，笔者将原来命令式编程风格的算法改造为函数式编程风格的Haskell代码：
- 外层for循环，被递归所替代
- 内层for循环，被filter所替代。
- 筛选的逻辑，使用Lambda表达式，以参数方式传入。
另外，本例也展示了使用函数式编程的2个特点：
- 代码量大幅减少。
- 函数式常见思维方式：把原始的数据List通过各种转化，变成我们需要的数据List。
（完）
