Leetcode 204, problem description:
Given an integer n, return the number of prime numbers that are strictly less than n.
Example 1:
Input: n = 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. Example 2:
Input: n = 0 Output: 0 Example 3:
Input: n = 1 Output: 0
Constraints:
0 <= n <= 5 * 10^6
Solutions
| Methods | Descriptions | Time Complexity | Result |
|---|---|---|---|
| Nested iteration | Step 1. Iterate from 2 to n to check every number if it’s a prime number. Step 2. To check if a number is prime, iterate all numbers less than it (to see if there is a number can exactly divide it) |
$O(n^2)$ | Time limit exceeded |
| Nested iteration with some optimizations | Step 1. Same as first method Step 2. Instead of iterating from 2 to number-1, narrow the range: 2 to sqrt(number) |
$O(n*(n!)^{1/2})$ | Time limit exceeded |
| Nested iteration with array record | Step 1. Create an array to record all prime numbers. Step 2. Iterate from 2 to n to check every number if it’s a prime number. If it’s prime number, add it to the array. Step 3. To check if a number is prime, iterate all numbers in the prime array(to see if the number can be exactly divided) |
Time limit exceeded | |
| Iteration with array record by using sieve of Eratosthenes | Step 1. Create an array, say recorder, with length n to record if a number if is prime. Assume 0 means prime number, 1 means non-prime number. By default, all elements of this array is 0.Step 2. Iterate from 2 to n to check every number if it’s a prime number. For the i-th number, first check if recorder[i] is 1. If it’s 1, then it’s not prime, continue to the next iteration; if it’s 0, then it’s a prime number, we will set all its multiples to 1 in recorder. Specifically, iterate from ii to n with incremenation i. That’s because the range i2 to i(i-1) with incremenation i has already been covered in less-than-i-th iteration. Notice, the index variable in iteration should be long or long long. The constraints of n is [0, 510^6], while the upper boundary might be 2^15-1 which is less than 5*10^6 because int variable only takes up 16 bits in some platforms. |
$O(nlog_2log_{2}n)$ | Accepted |