Question
Formatted question description: https://leetcode.ca/all/204.html
204 Count Primes
Count the number of prime numbers less than a nonnegative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
@taghashtable
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 n1 to record whether each number is marked. The reason for the length of n1 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)