素数是只有1和它自身两个约数的大于1的整数。即一个数是素数的充分必要条件如下：
给定一个正整数，如何通过程序判断它是否是素数，是本文要解决的问题。
我们可以用穷举法判断一个数是否为素数，从2开始到它本身，一个一个去除，只要能整除其中任意一个，它就不是素数。C代码如下：
int isPrime(long n)
{
if (n < 2)
{
return 0;
}
for (int i = 2; i <= n; i++) // 从1开始一路试到n
{
if (n % i == 0)
{
return 0;
}
}
return 1;
}
但是，上面这个方法，对于较大的数，性能比较差，我们似乎用不着尝试那么多数。 考虑到一个大于或等于2的数如果是合数，它必然能表示为另外两个大于或等于2的数的乘积。
假设a是合数，且 a = bc, b >= 2, c >=2
b 和 c 不可能同时大于a的平方根 sqrt(a)
证明：
如果 b > sqrt(a) 且 c > sqrt(a)
则 a = bc > sqrt(a) * sqrt(a) = a
得 a > a
矛盾。
衍生：
b 和 c 中必然有一个小于或等于 sqrt(a)
上面得到的结论对我们用计算机方法判定一个数是否为素数非常有用，我们最多只需要测试sqrt()这么多次数就行了，如此，前面的C代码可以改进为：
int isPrime(long n)
{
if (n < 2)
{
return 0;
}
for (int i = 2; i <= sqrt(n); i++) // 2 ~ sqrt(n)
{
if (n % i == 0)
{
return 0;
}
}
return 1;
}
完整的代码实现参prime.c，在Linux平台下，因为用到
$ gcc prime.c -o prime -lm
$ ./prime
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
TODO 其他语言实现
后记，因为阅读《算法·第4版》(Robert & Kevin)，书中第一章第13页提到求素数的算法，故做了一点小小的研究，记录于此。