CountPrimes [source code]
public class CountPrimes {
static
/******************************************************************************/
public class Solution {
public int countPrimes(int n) {
int count = 0;
for (int i = 0; i < n; i++) {
if (isPrime(i)) count++;
}
return count;
}
public boolean isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
int i = 5;
while (i <= n / i) { //division to avoid overflow
if (n % i == 0 || n % (i + 2) == 0) return false;
i += 6;
}
return true;
}
}
/******************************************************************************/
public static void main(String[] args) {
CountPrimes.Solution tester = new CountPrimes.Solution();
}
}
又是一个数学题, 反正优先掌握搜索的方法, 数学的方法反正也想不到, 等一下看discussion的时候再说了;
搜索其实也没有想到什么好的办法, 最后感觉还是要实现一个primality test. 这个算法是在Wiki上面看到的, 比最naive的线性搜应该是稍微快一点; primality test估计以后还是会碰到, 稍微记一下;
最后的速度是比较惨不忍睹的314ms (4%).
这题好像给了非常多的hint.
这个是hint里面给的穷搜法:
public int countPrimes(int n) {
int count = 0;
for (int i = 1; i < n; i++) {
if (isPrime(i)) count++;
}
return count;
}
private boolean isPrime(int num) {
if (num <= 1) return false;
// Loop's ending condition is i * i <= num instead of i <= sqrt(num)
// to avoid repeatedly calling an expensive function sqrt().
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}
这个是hint里面给出的另外一个解:
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;
}
是基于一个叫做Sieve of Eratosthenes 的算法;
其实仔细想想, 这个算法做到的加速的背后的核心原理并不是那么神秘, 如果时间足够, 按理应该是能够想出来的, 这个算法相对于我的穷搜的有点就在于, 是针对count本身做了大量的优化, 而不是我这个算法, 用最基本的思路来做一个overkill;
这里的comment里面提到一点: 用乘法代替求平方根是一个很聪明的做法. 不过他并没有比较乘法和除法之间的速度;
这个是discussion里的一个实现:
public int countPrimes(int n) {
if(n <=1 ) return 0;
boolean[] notPrime = new boolean[n];
notPrime[0] = true;
notPrime[1] = true;
for(int i = 2; i < Math.sqrt(n); i++){
if(!notPrime[i]){
for(int j = 2; j*i < n; j++){
notPrime[i*j] = true;
}
}
}
int count = 0;
for(int i = 2; i< notPrime.length; i++){
if(!notPrime[i]) count++;
}
return count;
}
一个小的优化就是让这个array flag代表的不再是isPrime, 而是notPrime, 这样就不用一开始初始化了; 直接默认not Prime全都是FALSE, 符合设定;
这个是submission最优解: 11(99), 就是用的这个算法:
public class Solution {
public int countPrimes(int n) {
if (n < 3) return 0;
boolean[] f = new boolean[n];
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;
}
}
这个算法是一个很聪明的优化, 刚开始也看不懂, discussion这个作者也是甩了个代码就跑了, 下面倒是有人解释:
This is a really clever solution, and it still scores in the top 1% of Java submissions.
There are a few realizations that are crucial to understanding its implementation:
- It inverts the true / false meanings in the traditional Sieve of Eratosthenes implementation.
true, here, means a composite number, not a prime. - It doesn't update the array values for any even numbers.
They all stay false, because changing them to true would be needless bookkeeping.
Here is my refactor of dojiangv's original post, with comments added:
public class Solution {
// Count the number of prime numbers less than a non-negative number, n
// @param n a non-negative integer
// @return the number of primes less than n
public int countPrimes(int n) {
// if n = 2, the prime 2 is not less than n,
// so there are no primes less than n
if (n < 3) return 0;
// Start with the assumption that half the numbers below n are
// prime candidates, since we know that half of them are even,
// and so _in general_ aren't prime.
//
// An exception to this is 2, which is the only even prime.
// But also 1 is an odd which isn't prime.
// These two exceptions (a prime even and a for-sure not-prime odd)
// cancel each other out for n > 2, so our assumption holds.
//
// We'll decrement count when we find an odd which isn't prime.
//
// If n = 3, c = 1.
// If n = 5, c = 2.
// If n = 10, c = 5.
int c = n / 2;
// Java initializes boolean arrays to {false}.
// In this method, we'll use truth to mark _composite_ numbers.
//
// This is the opposite of most Sieve of Eratosthenes methods,
// which use truth to mark _prime_ numbers.
//
// We will _NOT_ mark evens as composite, even though they are.
// This is because `c` is current after each `i` iteration below.
boolean[] s = new boolean[n];
// Starting with an odd prime-candidate above 2, increment by two
// to skip evens (which we know are not prime candidates).
for (int i = 3; i // i < n; i += 2) {
if (s[i]) {
// c has already been decremented for this composite odd
continue;
}
// For each prime i, iterate through the odd composites
// we know we can form from i, and mark them as composite
// if not already marked.
//
// We know that i // i is composite.
// We also know that i // i + i is composite, since they share
// a common factor of i.
// Thus, we also know that i // i + a//i is composite for all real a,
// since they share a common factor of i.
//
// Note, though, that i // i + i _must_ be composite for an
// independent reason: it must be even.
// (all i are odd, thus all i//i are odd,
// thus all (odd + odd) are even).
//
// Recall that, by initializing c to n/2, we already accounted for
// all of the evens less than n being composite, and so marking
// i // i + (odd)//i as composite is needless bookkeeping.
//
// So, we can skip checking i // i + a//i for all odd a,
// and just increment j by even multiples of i,
// since all (odd + even) are odd.
for (int j = i // i; j < n; j += 2 // i) {
if (!s[j]) {
c--;
s[j] = true;
}
}
return c;
}
}
这个解释的算是非常好了, 所以这个人的这个算法还是有很多小聪明的优化的; 按照下面的评论的说法, 这个算法确实是subtle optimizations, 不过人家确实是做到了99%了, 所以还是很厉害的;
Problem Description
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.
Difficulty:Easy
Total Accepted:117.3K
Total Submissions:442.2K
Contributor: LeetCode
Companies
amazon microsoft
Related Topics
hash table math
Similar Questions
Ugly Number Ugly Number II Perfect Squares
Problem Description
Hide Hint 1
Let's start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n. The runtime complexity of isPrime function would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better?
Hide Hint 2
As we know the number must not be divisible by any number > n / 2, we can immediately cut the total iterations half by dividing only up to n / 2. Could we still do better?
Hide Hint 3
Let's write down all of 12's factors:
2 × 6 = 12
3 × 4 = 12
4 × 3 = 12
6 × 2 = 12
As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n.
Our total runtime has now improved to O(n1.5), which is slightly better. Is there a faster approach?
public int countPrimes(int n) {
int count = 0;
for (int i = 1; i < n; i++) {
if (isPrime(i)) count++;
}
return count;
}
private boolean isPrime(int num) {
if (num <= 1) return false;
// Loop's ending condition is i * i <= num instead of i <= sqrt(num)
// to avoid repeatedly calling an expensive function sqrt().
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}
Hide Hint 4
The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n. But don't let that name scare you, I promise that the concept is surprisingly simple.
Sieve of Eratosthenes: algorithm steps for primes below 121. "Sieve of Eratosthenes Animation" by SKopp is licensed under CC BY 2.0.
We start off with a table of n numbers. Let's look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. What does this tell you? Should you mark off all multiples of 4 as well?
Hide Hint 5
4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible by 2 and were already marked off. So we can skip 4 immediately and go to the next number, 5. Now, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, ... can be marked off. There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off?
Hide Hint 6
In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, ... Now what should be the terminating loop condition?
Hide Hint 7
It is easy to say that the terminating loop condition is p < n, which is certainly correct but not efficient. Do you still remember Hint #3?
Hide Hint 8
Yes, the terminating loop condition can be p < √n, as all non-primes ≥ √n must have already been marked off. When the loop terminates, all the numbers in the table that are non-marked are prime.
The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n). For the more mathematically inclined readers, you can read more about its algorithm complexity on Wikipedia.
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;
}