根据维基百科定义，质数（Prime number），又称素数，指在大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。比1大但不是素数的数称为合数。1和0既非素数也非合数。质数在公钥加密算法（如RSA）中有重要的地位。
下边将会介绍几种较为常见的判断质/素数的方法：
1. 法一：最直接也最笨的方法
法一是按照质数的定义来考虑的，具体程序见下：
1 //*********************************** method 1 ***********************************//
2 bool IsPrime::isPrime_1(uint num)
3 {
4 bool ret = true;
5 for (uint i = 2; i < num - 1; i++)
6 {
7 if (num % i == 0)
8 {
9 ret = false;
10 break;
11 }
12 }
13
14 return ret;
15 }
2. 法二：将循环判断次数减少一半（大约）
对于一个正整数num而言，它对(num/2, num)范围内的正整数是必然不能够整除的，因此，我们在判断num的时候，没有必要让它除以该范围内的数。代码如下：
1 //*********************************** method 2 ***********************************//
2 bool IsPrime::isPrime_2(uint num)
3 {
4 bool ret = true;
5 uint ubound = num / 2 + 1;
6 for (uint i = 2; i < ubound; i++)
7 {
8 if (num % i == 0)
9 {
10 ret = false;
11 break;
12 }
13 }
14
15 return ret;
16 }
3. 法三：在法二的基础上继续提高
对于一个小于num的正整数x，如果num不能整除x，则num必然不能整除num/x （num = num/x * x）。反之相同。我们又知num =√num*√num。 如果n除以大于√num的数，必得到小于√num的商，而小于√num的整数已经在2到√num的整数试过了，因为就没有必要再试（√num, num）范围内的数了。代码如下：
注：经常会看到别人说“一个数 n 如果是合数，那么它的所有的因子不超过sqrt(n)”。这句话是错误的。举一个例子，16的因子包括了1、2、4、8，但很明显8>√16。另外，因子跟因数是不一样的，因数还会包括数本身，如16的因数为1、2、4、8、16。
1 //*********************************** method 3 ***********************************//
2 bool IsPrime::isPrime_3(uint num)
3 {
4 bool ret = true;
5 uint ubound = sqrt(num) + 1;
6 for (uint i = 2; i < ubound; i++)
7 {
8 if (num % i == 0)
9 {
10 ret = false;
11 break;
12 }
13 }
14
15 return ret;
16 }
4. 法四：考虑偶数的因素
我们都知道，除了2之外，其他所有的偶数（正整数）全都不是质数，因为它们都能被2整除。代码改进如下：
1 //*********************************** method 4 ***********************************//
2 bool IsPrime::isPrime_4(uint num)
3 {
4 bool ret = true;
5 if (num == 2)
6 return ret;
7
8 // it is no need to consider even numbers larger than 2
9 if (num % 2 != 0)
10 {
11 uint ubound = sqrt(num) + 1;
12 for (uint i = 2; i < ubound; i++)
13 {
14 if (num % i == 0)
15 {
16 ret = false;
17 break;
18 }
19 }
20 }
21 else
22 {
23 ret = false;
24 }
25
26 return ret;
27 }
5. 法五：埃拉托斯特尼筛选法
当我们判断某个取值范围内的素数有哪些的时候，有一个方法非常可行，就是埃拉托斯特尼筛选法。这个算法效率很高，但占用空间较大。
我们知道，一个素数p只有1和p这两个约数，并且它的约数一定不大于其本身。因此，我们下边方法来筛选出来素数：
1）把从2开始的、某一范围内的正整数从小到大顺序排列； 2）剩下的数中选择最小的素数，然后去掉它的倍数。
3）依次类推，直到循环结束。
这种筛选法动态图如下：
程序如下：
1 //*********************************** method 5 ***********************************//
2 // find prime numbers between [lower bound, upper bound)
3 vector
4 {
5 assert(lbound >= 0);
6 assert(ubound >= 0);
7 assert(lbound <= ubound);
8
9 vector
10 for (int i = 0; i < ubound; i++)
11 isprime.push_back(true);
12
13 for (int i = 2; i < ubound; i++)
14 {
15 for (int j = i + i; j < ubound; j += i)
16 {
17 isprime[j] = false;
18 }
19 }
20
21 vector
22 for (int i = lbound; i < ubound; i++)
23 {
24 if (i != 0 && i != 1 && isprime[i])
25 ret.push_back(i);
26 }
27
28 return ret;
29 }
6. 法六：去除法五中不必要的循环
对于法五来说，即使isprime中已经被判断为false的元素，它以及它的倍数还会被重新赋值为false（可能会有很多遍），而实际上已经没有必要这样子做。例如，第2个元素的倍数第4、6、8、10...个元素已经被判定为false，但循环到第4个元素的时候，第8、12、16...个元素还会被重新赋值，这有点重复。因此，我们要去掉这些重复的工作。代码比较简单，只需要加一语句即可，见下：
1 //*********************************** method 6 ***********************************//
2 // find prime numbers between [lower bound, upper bound)
3 vector
4 {
5 assert(lbound >= 0);
6 assert(ubound >= 0);
7 assert(lbound <= ubound);
8
9 vector
10 for (int i = 0; i < ubound; i++)
11 {
12 if (i < 2)
13 isprime.push_back(false);
14 else
15 isprime.push_back(true);
16 }
17
18 for (int i = 2; i < ubound; i++)
19 {
20 if (isprime[i])
21 {
22 for (int j = i + i; j < ubound; j += i)
23 {
24 isprime[j] = false;
25 }
26 }
27 }
28
29 vector
30 for (int i = lbound; i < ubound; i++)
31 {
32 if (isprime[i])
33 ret.push_back(i);
34 }
35
36 return ret;
37 }
7. 法七：大综合（结合法三及法六）
法七是结合了法三及法六，代码如下：
1 //*********************************** method 7 ***********************************//
2 // find prime numbers between [lower bound, upper bound)
3 vector
4 {
5 assert(lbound >= 0);
6 assert(ubound >= 0);
7 assert(lbound <= ubound);
8
9 vector
10 for (int i = 0; i < ubound; i++)
11 {
12 if (i < 2)
13 isprime.push_back(false);
14 else
15 isprime.push_back(true);
16 }
17
18 uint ulimit = sqrt(ubound) + 1;
19 for (int i = 2; i < ulimit; i++)
20 {
21 if (isprime[i])
22 {
23 uint repeat = ubound / i;
24 for (int j = 2; j < repeat; j++)
25 {
26 isprime[i * j] = false;
27 }
28 }
29 }
30
31 vector
32 for (int i = lbound; i < ubound; i++)
33 {
34 if (isprime[i])
35 ret.push_back(i);
36 }
37
38 return ret;
39 }
整个程序代码（包括单元测试代码）见Github.
更多的方法请参见百度文库上的一篇文章。