一、题目

地址:https://leetcode.com/problems/count-primes/

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10

输出: 4

解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

二、解法

分析：比较2~ n-1，之间的数是否为质数

如何判断一个数M是否为质数呢？如果M能够被小于M的数整除，那么M就不是质数。否则为质数。

1、解法1

思路：这种方式比较好理解，对于任何一个数M，只需要从2开始，一直到小于其自身，依次判断能否被M整除，能则不是质数，都不能整除则为质数。

func countPrimes(n int) int {
   var count int
   for i := n - 1; i >= 2; i -- {
      //判断i是否为质数
      var isPrime bool = true
      for j := 2; j < i; j ++ {
         if i%j == 0 { //不是一个质数
            isPrime = false
            break
         }
      }
      if isPrime {
         count++
      }
   }

   return count
}

2、解法2

思路：解法1中，针对每个数n都遍历n-1次，其实是很浪费的。我们知道，如果一个大于1的数M，不是质数，那么必然存在两个约数m1，m2， m1 * m2 = M。根据这个发现，我们判断M是否为质数，只需要判断m1，不需要判断m2。以此内推M的有很多对m1和m2，即(ma1, mb1)，(ma2, mb2)，(ma3, mb3)。。。。(man, mbn)，假设man 不大于mbn，那么我们仅仅需要比较(ma1,ma2,ma3.....man)是否为质数即可。那么man是多少呢？我们知道man * mbn = M，man <= mbn，所以可以得出 man * man = M，进而求出man的最大值。所以，每次仅仅需要比较到 math.Sqrt(M)为止。

func countPrimes(n int) int {
   var count int
   for i := n - 1; i >= 2; i -- {
      //判断i是否为质数
      var isPrime bool = true
      for j := 2; j <= int(math.Sqrt(float64(i))); j ++ {
         if i%j == 0 { //不是一个质数
            isPrime = false
            break
         }
      }
      if isPrime {
         count++
      }
   }

   return count
}

三、补充

1、什么是质数

质数，又被称为素数。就是在所有比1大的整数中，除了1和它本身以外，不再有别的因数，这种整数叫做质数。

和质数相对应的是合数，指的是除了能被1和本身整除外，还能被其他数（0除外）整除的数。

备注：1既不是质数，也不是合数