Leetcode 204. Count Primes

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Input: n = 0
Output: 0
Input: n = 1
Output: 0
  • 0 <= n <= 5 * 106
  1. create a boolean array and default them as true
  2. change them to false if there you can multiple them
  1. if already change to false, don’t need to change and scan again
  2. for (int j = i*i; j < n; j+= i)
  1. use notPrime

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Gary Chiang

Gary Chiang

19 Followers

CS new grad, 6 years experience related to supply chain management. Located in Bay area