素数（质数）

质数和素数是同一个概念，都是指只能被1和自身整除的正整数。换言之，如果一个正整数大于1，且只有1和它本身这两个因数，那么这个数就是质数或素数。

判断质数

判断一个数是否为质数或素数，可以使用多种方法，下面介绍两种比较常用的方法：

试除法

对于一个大于1的整数n，如果它在2到sqrt(n)这个范围内的所有正整数中都无法被整除，那么它就是质数。其中，sqrt表示求平方根。例如，判断17是否为质数，只需要在2到4（sqrt(17)取整）之间逐一尝试，发现它不能被2、3、4整除，因此是质数。

算法详解

bool isPrime(int count) {
  if (count < 2)
    return false;
  for (int i = 2; i <= sqrt(count); i++) {
    if (count % i == 0)
      return false;
  }
  return true;
}

埃拉托斯特尼筛法

这是一种筛选法，可以用来找出一定范围内的所有质数。具体实现方法是先把所有自然数标记为未筛选，然后从2开始，将2的倍数标记为合数，接着找到标记为未筛选的最小的数，再将它的倍数标记为合数，依次进行下去，直到筛完所有小于等于目标范围的自然数。最终剩下的未被标记的数就都是质数。

举个例子，我们要找出小于等于20的所有质数。首先列出这些数：2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20。然后从2开始，把它的倍数4、6、8、10、12、14、16、18、20全部标记为合数。接着轮到3，把它的倍数6、9、12、15、18标记为合数。最后，剩下的未被标记的数就是质数：2、3、5、7、11、13、17、19。

筛法是一种高效的算法，其时间复杂度大约是O(n log log n)，其中n是要筛选的范围内的自然数个数。

算法详解

void eratosthenes() {
  for (int i = 2; i < arr.size(); i++) {
    if (!arr[i]) {
      for (int j = 2; i * j < arr.size(); j++) {
        arr[i * j] = true;
      }
    }
  }
}