题目：统计所有小于非负整数 n 的质数的数量
0 <= n <= 5000000
示例 1：输入：n = 10， 输出：4 ， 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7
示例 2：输入：n = 0 ，输出：0；输入：n = 1 ，输出：0
思路：n=0，1，2时，容易得到数量为0；n>2时，遍历[3,n）的所有整数，判断是否为质数
先提下数学基础：质数也叫素数，n（n>1）为素数当且仅当n只有1和n两个因子（就是约数）
另外，一个非负自然数的因子总是成对出现，因为是整除，总有除数和商，就是他俩
解答
第一次提交：
class Solution { public int countPrimes(int n) { if (n == 0 || n == 1 || n == 2) { return 0; } int count = 0; for (int i = 2; i < n; i++) { boolean isPrime = true; for (int j = 2; j < i; j++) {-----------------------范围缩小 if (i % j == 0) { isPrime = false; break; } } if (isPrime) { count++; } } return count; } }
提交：超时...............这里很容易想到，在判断是否为素数时，其实不需要判断到i-1,只用判断到[2,i/2]即可
修改提交：
class Solution { public int countPrimes(int n) { if (n == 0 || n == 1 || n == 2) { return 0; } int count = 0; for (int i = 2; i < n; i++) { boolean isPrime = true; for (int j = 2; j <= i/2; j++) {-----------------------范围需要继续缩小 if (i % j == 0) { isPrime = false; break; } } if (isPrime) { count++; } } return count; } }
提交--------->超时，提示是在n=499979时超时的；看起来还要优化，那就从数学角度，这次修改，j的上界是i/2，
这是因为从2开始遍历的，而2是最小的素数；一个自然数的约数总是成对出现，那在上面的提示位置，可以在判断
i不能整除j时，将上界继续缩小；可以定义一个变量high初始值为i/2,并随着j变化：high=i/j;
修改提交：
class Solution { public int countPrimes(int n) { if (n == 0 || n == 1 || n == 2) { return 0; } int count = 0; for (int i = 2; i < n; i++) { boolean isPrime = true; int high = i/2; for (int j = 2; j < i; j++) {-----------------------范围需要继续缩小 if(j>high){ break; } if (i % j == 0) { isPrime = false; break; } high = i/j; } if (isPrime) { count++; } } return count; } }
提交-------------->呵呵呵，还是超时，提示是在n=1500000，优化起效了，于是继续探索
如果我判断了不能被2整除，还需要判断能不能被4，8，16...这些数整除吗？不需要
如果我判断了不能被3整除，还需要判断能不能被6，9，12...这些数整除吗？不需要
如果我判断了不能被7整除，还需要判断能不能被14，35，49...这些数整除吗？也不需要
我们已知所有合数均能分解为一个个质因子，所以，对一个自然数n,只需要遍历所有小于n的质数，如果n都不能整除它们，
那n就是素数，正好第一层的循环可以保存所有上一次判断出来的质数，为了一步到位，前面探索high的定义结合在一起
修改提交：
public class Solution { public static int countPrimes(int n) { if (n == 0 || n == 1 || n == 2) { return 0; } int count = 0; List<Integer> list = new ArrayList<>(); for (int i = 2; i < n; i++) { boolean isPrime = true; int high = i / 2; for (int j = 0; j < list.size(); j++) { int a = list.get(j); if (a > high) { break; } if (i % a == 0) { isPrime = false; break; } high = i / a; } if (isPrime) { count++; list.add(i); } } return count; } }