LeetCode(Math)Count Primes

2018-06-18

Count Primes

Count the number of prime numbers less than a non-negative number, n.

Example:

1
2
3

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

思路：找出小于n的质数的个数。首先能想到质数的特性就是：只能被1和它本身整除的数，而我们如果利用这样的特性刚正面来解决的话只要定义一个辅助函数isPrime()判断出这个数是不是质数然后在主函数里边调用这个函数判断从2到n中满足条件的数即可。

代码如下：

class Solution {
    public int countPrimes(int n) {
        int count=0;
        for(int i=2;i<n;i++){
            if(isPrime(i)){
                count++;
            }
        }
        return count;
    }
    public boolean isPrime(int n){
        int count=0;
        for(int i=1;i<=n;i++){
            if(n%i==0){
                count++;
            }
            if(count>2){
                return false;
            }
        }
        if(count==2){
            return true;
        }
        return false;
    }
}

　　以上代码虽然很好理解，但是运行超时，需要优化算法，减少计算量。每一次都去判断这个数是不是质数其实是很大的计算量，因为质数本来就少，而每次对非质数都进行质数的判断运算，复杂度较高，考虑利用质数的特性在计算中就排除掉大部分的非质数，在运算中就将一些数淘汰掉。考虑：如果一个质数乘以2,3,4，…直到乘积小于n为止的所有数应该都不是质数。

代码如下：

class Solution {
    public int countPrimes(int n) {
        boolean [] notPrime=new boolean [n];
        int count=0;
        for(int i=2;i<n;i++){
            if(notPrime[i]==false){
                count++;
            }
            for(int j=2;i*j<n;j++){
                notPrime[i*j]=true;
            }
        }
        return count;
    }
}

　　以上代码定义了一个辅助判断矩阵，初始全为false，表示不是质数，即初始认为全是质数，随后，从2开始，记录质数的数量count，然后对当前数乘2,3,4…的操作，并使对应的辅助矩阵下标对应值更改为true,即表示非质数。这样在循环计算中可以大大减少计算量，在判断的同时生成非质数的数，大大减少了判断次数，运行通过。