[LeedCode]Count Primes素数个数

本文主要是介绍[LeedCode]Count Primes素数个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode题目：
Description:

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

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

思路( Sieve of Eratosthenes方法 )：

public class Solution {public int countPrimes(int n) {if(n == 0) return 0;boolean[] array = new boolean[n];for (int i = 0;i < n;i++) array[i] = true;array[0] = false;int count = 0;int limit = (int) Math.sqrt(n);for(int i = 2; i <= limit; i++) {if (array[i-1]) {for (int j = i*i; j < n; j += i) {array[j - 1] = false;}}}for (int j = 2; j < n; ++j) {if (array[j]) ++count;}return count;} 
}

参考博客：http://www.cnblogs.com/grandyang/p/4462810.html

这篇关于[LeedCode]Count Primes素数个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---