1847. Prime Factor Counts
A lab labels every number from 1 to n by how many different primes divide it. The number 12 is divisible by the primes 2 and 3, so its label is 2. The number 8 is divisible only by 2, so its label is 1, and the number 1 has no prime divisor, so its label is 0.
Return an array of length n where entry i - 1 is the label of the number i. Factoring each number on its own repeats work, so use a sieve: whenever you meet a number that no smaller prime has touched, it is prime, and you add 1 to all of its multiples. Aim for O(n log log n) time and O(n) extra space.
Example 1
- Input:
- n = 12
- Output:
- [0,1,1,1,1,2,1,1,1,2,1,2]
- Explanation:
Entry 6 is 2 because 6 = 2 * 3, and entry 12 is 2 because 12 = 2 * 2 * 3.
Example 2
- Input:
- n = 1
- Output:
- [0]
- Explanation:
The number 1 has no prime divisor.
Example 3
- Input:
- n = 30
- Output:
- [0,1,1,1,1,2,1,1,1,2,1,2,1,2,2,1,1,2,1,2,2,2,1,2,1,2,1,2,1,3]
- Explanation:
30 = 2 * 3 * 5, so entry 30 is 3.
Constraints
1 ≤ n ≤ 2000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log log n)
- Space
- O(n)