204. Count Primes

  • 26.2%

https://leetcode.com/problems/count-primes/?tab=Description

Description:

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


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?
  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?
  3. Let’s write down all of 12’s factors:
1
2
3
4
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?

  1. 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.

image

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?

  1. 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?

  2. 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?

  3. 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?

  4. 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.

对于非质数,可以分解为多个质数的乘积,所以保存前面的质数,遇到下一个,只要检查是否能被前面保存的质数整除就可以判断是否为质数了。


方法一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}

方法二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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) { // 此处方法不错,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;
}

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int countPrimes(int n) {
if(n<=1) return 0;
vector<int> v(n+1, 1);
for(int i=2; i*i<=n; i++){
if(v[i]==0)
continue;
for(int j=i*i; j<n; j+=i){
v[j] = 0;
}
}
int res = 0;
for(int i=2; i<n; i++)
res += v[i]==1;
return res;
}
};

另一种实现:

学习一个是使用bool类型, vector

一个是count的使用return count(prime.begin(), prime.end(), true)

https://discuss.leetcode.com/topic/17034/short-c-sieve-of-eratosthenes-solution

Short C++ Sieve of Eratosthenes solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int countPrimes(int n) {
vector<bool> prime(n, true);
prime[0] = false, prime[1] = false;
for (int i = 0; i < sqrt(n); ++i) {
if (prime[i]) {
for (int j = i*i; j < n; j += i) {
prime[j] = false;
}
}
}
return count(prime.begin(), prime.end(), true);
}
};

方法三:

https://discuss.leetcode.com/topic/12910/my-easy-one-round-c-code

My easy one round c++ code

特别注意 if(i>upper) continue;这句话,不加这句话会超时。对于大于sqrt(n)的不必再求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int countPrimes(int n) {
if (n<=2) return 0;
vector<bool> passed(n, false);
int sum = 1;
int upper = sqrt(n);
for (int i=3; i<n; i+=2) {
if (!passed[i]) {
sum++;
//avoid overflow
if (i>upper) continue;
for (int j=i*i; j<n; j+=i) {
passed[j] = true;
}
}
}
return sum;
}

https://discuss.leetcode.com/topic/20525/simple-16-ms-10-line-c-solution-1-use-new-bool-array-2-only-traverse-odd-numbers-3-count-and-sieve-at-the-same-time

Simple 16 ms,10 line C++ solution. 1.use new bool array 2. only traverse odd numbers 3.count and sieve at the same time

use new bool array. 2. only traverse odd numbers. 3. count and sieve at the same time.

trick 1, thanks to 27ms,16 lines, C++ solution

trick 2, for the inspiration, thanks to my C solutions in 13ms,use Sieve of Eratosthenes and only test 6n-1 and 6n+1

trick 3, thanks to my C solutions in 44ms, time nearly O(n), and space nearly O(n) and my easy one round c++ code

1
2
3
4
5
6
7
8
9
10
11
12
int countPrimes(int n) {
if (n <= 2) return 0;
int res=n>>1, m=sqrt(n-1); // intilize res to n/2, removes all even number(not 2) and 1
bool *table=new bool[n];
for(int i=3,j,step;i<=m;i+=2)
if(!table[i]) { // i is an odd prime
for(step=i<<1, j=i*i;j<n;j+=step) // step=i*2, ignore even numbers
if(!table[j]) { table[j]=1; --res; }
}
delete []table;
return res;
}

python


https://discuss.leetcode.com/topic/14036/fast-python-solution

Fast Python Solution

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
# @param {integer} n
# @return {integer}
def countPrimes(self, n):
if n < 3:
return 0
primes = [True] * n
primes[0] = primes[1] = False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
return sum(primes)

谢谢你,可爱的朋友。