Smallest Prime Factor Sieve
MediumMathArraySorting
Description
Given an integer n ≥ 2, return an array of length n-1 whose i-th element (0-indexed) is the smallest prime factor of i+2.
Examples
Input:
n = 5Output:
[2,3,2,5]Explanation:
Indices map to integers 2..5; their smallest prime factors are 2, 3, 2, 5 respectively.
Input:
n = 2Output:
[2]Explanation:
With n = 2 the array has length 1 and contains only the smallest prime factor of 2, which is 2.
Input:
n = 10Output:
[2,3,2,5,2,7,2,3,2]Explanation:
Smallest prime factors for 2..10 are 2,3,2,5,2,7,2,3,2 in order.
Constraints
- •
2 ≤ n ≤ 10⁴