Question

Formatted question description: https://leetcode.ca/all/204.html

 204	Count Primes

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

 Example:

 Input: 10
 Output: 4

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

 @tag-hashtable

Algorithm

Traverse from 2 to the root number n, find the first prime number 2, and then mark all its multiples, then to the next prime number 3, mark all its multiples, and so on, until the root number n, then the unmarked numbers in are prime numbers.

We need a bool array of length n-1 to record whether each number is marked. The reason for the length of n-1 is that the title says it is the number of prime numbers less than n, not including n.

Code

Java

import java.util.Arrays;

public class Count_Primes {


    class Solution {
        public int countPrimes(int n) {
            int res = 0;
            boolean[] isPrime = new boolean[n];
            Arrays.fill(isPrime, true);

            for (int i = 2; i < n; ++i) {
                if (!isPrime[i]) {
                    continue;
                }
                ++res;
                for (int j = 2; i * j < n; ++j) {
                    isPrime[i * j] = false;
                }
            }
            return res;
        }
    }
}

```
Todo
```

class Solution(object):

  def countPrimes(self, n):
    """
    :type n: int
    :rtype: int
    """

    def helper(n, dp):
      for i in range(2, n):
        if dp[i] == 1:
          k = i * i
          if k >= n:
            return
          while k < n:
            dp[k] = 0
            k += i

    if n < 2:
      return 0
    ans = 0
    dp = [1] * n
    dp[0] = 0
    dp[1] = 0
    helper(n, dp)
    # for i in range(0, n):
    #     if dp[i] == 1:
    #         print i + 1

    return sum(dp)

204 - Count Primes

Question

Algorithm

Code

All Problems

All Solutions