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)