题目描述（简单难度）

204. Count Primes - 图1

求出小于 n 的素数个数。

解法一

遍历 2 到 n - 1 ，依次判断当前数是否是素数。

判断 n 是否是素数，只需要判断 2 到 n - 1 是否是 n 的因子，如果有一个是，那就表明 n 不是素数。

判断素数可以做一个优化，那就是不需要判断 2 到 n - 1，只需要判断2 到 sqrt(n) 也就是根号 n 即可。因为如果存在超过根号 n 的因子，那么一定存在小于根号 n 的数与之对应。

  1. public int countPrimes(int n) {
  2.     int count = 0;
  3.     for (int i = 2; i < n; i++) {
  4.         if (isPrime(i)) {
  5.             count++;
  6.         }
  7.     }
  8.     return count;
  9. }
  11. private boolean isPrime(int n) {
  12.     int sqrt = (int) Math.sqrt(n);
  13.     for (int i = 2; i <= sqrt; i++) {
  14.         if (n % i == 0) {
  15.             return false;
  16.         }
  17.     }
  18.     return true;
  19. }

解法二

空间换时间，参考 这里。

用一个数组表示当前数是否是素数。

然后从 2 开始，将 2 的倍数，4、6、8、10 …依次标记为非素数。

下个素数 3，将 3 的倍数，6、9、12、15 …依次标记为非素数。

下个素数 7，将 7 的倍数，14、21、28、35 …依次标记为非素数。

在代码中，因为数组默认值是 false ，所以用 false 代表当前数是素数，用 true 代表当前数是非素数。

  1. public int countPrimes(int n) {
  2.     boolean[] notPrime = new boolean[n];
  3.     int count = 0;
  4.     for (int i = 2; i < n; i++) {
  5.         if (!notPrime[i]) {
  6.             count++;
  7.             //将当前素数的倍数依次标记为非素数
  8.             for (int j = 2; j * i < n; j++) {
  9.                 notPrime[j * i] = true;
  10.             }
  11.         }
  12.     }
  13.     return count;
  14. }

总

解法二中空间换时间的思想在编程中经常用到。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情