1, 题目

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

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

2, 算法

  1. object Solution {
  2.     def countPrimes(n: Int): Int = {
  3.         if (n < 2) {
  4.             return 0
  5.         }
  6.         val arr = Array.fill(n)(1)
  7.         arr(0) = 0
  8.         arr(1) = 0
  9.         for (i <- 2 to scala.math.sqrt(n).toInt) {
  10.             var j = 2 * i
  11.             while (j < n) {
  12.                 arr(j) = 0
  13.                 j += i
  14.             }
  15.         }
  16.         arr.sum
  17.     }
  18. }
  1. class Solution:
  2.     def countPrimes(self, n: int) -> int:
  3.         if n < 2:
  4.             return 0
  5.         result = [1] * n
  6.         result[0] = 0
  7.         result[1] = 0
  8.         import math
  9.         import functools
  10.         for i in range(2, int(math.sqrt(n)) + 1):
  11.             j = 2 * i
  12.             while j < n:
  13.                 result[j] = 0
  14.                 j += i
  15.         return functools.reduce(lambda x, y: x + y, result)