204-计数质数
访问量:1040

一、题目

地址: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既不是质数,也不是合数