204.[LeetCode]count primes

列出 n 之前所有的 质数（只能被它和它自己整除的数）

思路一：

对于n之前的每一个数，都做一次 isPrimes() 的判断，isPrimes方法主要就是判断n是否可以被比它小的数整除。

这样时间复杂度是 O(n2)

更好：

试想，一个数n有可能被 比 n/2 更大的数 整除吗？不可能的

所以 IsPrimes() 方法中，每次判断到 n/2 就可以了

更好II：

2*6 = 12

3*4 = 12

4*3 = 12

6*2 = 12

在这其中，2*6和3*4是完全不必计算的，和之后的重复了，如何避免这种重复呢？

循环的时候，我们可以进一步的将 上限 压到 根号2

此时时间复杂度为 O(n1.5)

---

最高效率的方法 Sieve of Eratosthenes

时间复杂度只要 O(n)

假设有 n = 100

首先2是质数，那么2的倍数肯定都不是质数,可以去掉

然后向后找遇到的第一数是3，那么3肯定是质数 (因为在这种策略下，向后的第一数都有一个性质，此数不是之前所有数的倍数，也即是质数)

然后一直向后推到10，10是100开根号的结果，之前是讨论过的，100以内大于10的非质数数，肯定会有小于10的因子，也就是之前肯定排除了

剩下的数就全是质数了！

java代码如下：

1 不是质数 也不是合数

// 求比n小的质数的个数 public class Solution { public int countPrimes(int n) { if(n == 1||n == 0) return 0; int count = 0; int[] nums = new int[n]; for(int i = 0; i < n; i++){ nums[i] = i; } // start count int primes = 2; double upbound = Math.sqrt(n); while(primes <= upbound){ if(nums[primes]!=0){ int j = 2; while(primes*j <= n-1){ nums[primes*j] = 0; j++; } } primes++; } // for(int i = 0; i < n; i++){ if(nums[i]!=0) count++; } return count-1; // 1不是质数 } }

大神代码：

public int countPrimes(int n) { boolean[] isPrime = new boolean[n]; for (int i = 2; i < n; i++) { isPrime[i] = true; } // Loop's ending condition is i * i < n instead of i < sqrt(n) // to avoid repeatedly calling an expensive function sqrt(). for (int i = 2; i * i < n; i++) { if (!isPrime[i]) continue; for (int j = i * i; j < n; j += i) { isPrime[j] = false; } } int count = 0; for (int i = 2; i < n; i++) { if (isPrime[i]) count++; } return count; }

Tips:

因为题目要求只是count，所以明显用boolean值就可以，没有必要对么一个进行赋值

在求开根号的范围的时候，用了 i*i = n 作为边界，比我调用Math.sqrt() 要更简洁

---

最强代码 beats 97.5

public int countPrimes(int n) { if (n < 3) return 0; boolean[] f = new boolean[n]; //Arrays.fill(f, true); boolean[] are initialed as false by default int count = n / 2; for (int i = 3; i * i < n; i += 2) { if (f[i]) continue; for (int j = i * i; j < n; j += 2 * i) { if (!f[j]) { --count; f[j] = true; } } } return count; }