LeetCode：Count Primes - 统计质数数量

1、题目名称

Count Primes（统计质数数量）

2、题目地址

https://leetcode.com/problems/count-primes/

3、题目内容

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

中文：统计正整数n以内（不含n本身）质数的数量

4、一个TLE的方法

从1到n，考察每个数字是否为质数。这个方法由于花费时间较长，不能满足题目中对时间的要求。

一段实现此方法的Java代码如下：

/**
 * 功能说明：LeetCode 204 - Count Primes
 * 开发人员：Tsybius2014
 * 开发时间：2015年9月6日
 */
public class Solution {
    
    /**
     * 计算n以下的质数数量
     * @param n 正整数
     * @return n以下的质数数量
     */
    public int countPrimes(int n) {
        
        if (n <= 1) {
            return 0;
        }
        
        int result = 0;
        boolean isPrime = true;
        for (int i = 2; i < n; i++) {

            //判断数字i是否为质数
            isPrime = true;
            if (i == 2 || i == 3 || i == 5 || i == 7) {
                isPrime = true;
            } else if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
                isPrime = false;
            } else {
                for (int j = 2; j <= Math.sqrt(i); j++) {
                    if (i % j == 0) {
                        isPrime = false;
                        break;
                    }
                }
            }
            
            //如果i是质数result自增1
            if (isPrime) {
                result++;
            }
        }
        
        return result;
    }
}

4、解题方法

另一个求质数的方法是埃拉托斯特尼筛法（Sieve of Eratosthenes），这个方法需要声明一个非常大的数组，但速度较上面的方法要快很多。

一段实现此方法的Java代码如下：

/**
 * 功能说明：LeetCode 204 - Count Primes
 * 开发人员：Tsybius2014
 * 开发时间：2015年9月6日
 */
public class Solution {
    
    /**
     * 计算n以下的质数数量
     * @param n 正整数
     * @return n以下的质数数量
     */
    public int countPrimes(int n) {
        
        if (n <= 1) {
            return 0;
        }

        int result = 0;
        boolean[] arr = new boolean[n];
        for (int i = 2; i < n; i++) {
            
            //如果arr[i]是质数则将其倍数全部标记为合数，否则不予考虑
            if (!arr[i]) {
                result++;
            } else {
                continue;
            }

            int j = 2;
            while (i * j < n) {
                arr[i * j] = true;
                j++;
            }
        }
        
        return result;
    }
}

END

转载于:https://my.oschina.net/Tsybius2014/blog/501952