什么是Eratosthenes筛法
考虑一个常见的数论问题，指定一个整数，求出不大于该数的所有质数。我们可以先写一个函数来判断某个整数是否为质数，然后用它逐一判断每个整数，而Eratosthenes筛法比这种方法高效得多。
下面举例来说明它的原理。观察下面的彩图（来自wikipedia），这里是检查120以内的所有质数。首先去掉1，因为1既不是质数也不是合数；然后2是质数，那么2的倍数都肯定不是质数了，所以把2的倍数都涂成红色（它们出局了，这里是质数的游戏...）；接下来3没有被涂掉，所以3是质数，同理把3的倍数涂成绿色；下一个未涂掉的是5，所以5也是质数，同理把5的倍数涂掉；然后再涂掉7的倍数，剩下的就都是质数了。
怎么，只要看2、3、5、7就够了？这里有两个不那么容易确定的问题，一是如何依次断定3、5、7都是质数；二是为何涂掉7的倍数后就完成了。对于问题一，如果一个整数不能被比它小的所有质数整除（这里就是没被涂掉），那么我们就可以断定它是质数。另外，该筛法的依据是，对于整数n，如果它不能被不大于n的平方根(Sqrt(n))的任何质数所整除，那么n就是质数。这样就解决了问题二，对于120以内的整数，如果它不是质数，那么它必定能被不大于10的质数（也就是2、3、5、7）所整除。
这样我们可以确信上述算法是正确的了，下面来看看如何实现它。
Eratosthenes筛法的C#和F#实现
C# Code - Eratosthenes筛法
// 返回不大于n的质数构成的数组
public static int[] SieveOfEratosthenes(int n)
{
if (n < 2) { return new int[0]; }
// Init sieve.
bool[] sieve = new bool[n + 1];
for (int i = 2; i < sieve.Length; i++) { sieve[i] = true; }
// Check it.
int upperBound = Convert.ToInt32(Math.Sqrt(n));
for (int i = 2; i <= Math.Sqrt(n); i++)
{
if (sieve[i])
{
for (int j = i + i; j <= n; j += i)
{
sieve[j] = false;
}
}
}
// Count it.
int count = 0;
for (int i = 2; i < sieve.Length; i++)
{
if (sieve[i])
{
count++;
}
}
// Generate the result.
int[] primes = new int[count];
int index = 0;
for (int i = 2; i < sieve.Length; i++)
{
if (sieve[i])
{
primes[index++] = i;
}
}
return primes;
}
下面是F#实现，其中getInt和main是辅助函数：
F# Code - Eratosthenes筛法
#light
open System
let generatePrimes n =
match n with
| _ when n < 2 -> [||]
| _ ->
// Init sieve.
let sieve = [| for i in 0 .. n do yield true |]
let isPrime index = sieve.[index]
// Check it.
let upperBound = Convert.ToInt32(Math.Sqrt((float)n))
for i = 2 to upperBound do
if isPrime i then
for j in [i * 2 .. i .. sieve.Length - 1] do
sieve.[j] <- false
let mutable count = 0
for i = 2 to sieve.Length - 1 do
if isPrime i then
count <- count + 1
let primes = Array.create count 0
let mutable index = 0
for i = 2 to sieve.Length - 1 do
if isPrime i then
primes.[index] <- i
index <- index + 1
primes
let getInt() =
Convert.ToInt32(Console.ReadLine())
let main() =
let i = getInt()
let primes = generatePrimes i
Console.WriteLine("find {0} prime(s)", primes.Length)
print_any primes
main()
Console.Read()
这两段代码也就勉强能实现算法吧，有时间再考虑优化一下。
（要了解本人所写的其它F#随笔请查看 F#系列随笔索引）
参考：
本文转自一个程序员的自省博客园博客，原文链接：http://www.cnblogs.com/anderslly/archive/2008/11/11/fsharp-sieve-of-eratosthenes.html，如需转载请自行联系原作者。
