Math Primes and the sieve
98. Prime Factorisation
Given an array of positive integers nums, return the prime factorisation of every number in it.
The prime factorisation of a number is the list of primes that multiply to give it. For example,
12 = 2 × 2 × 3, so the factorisation of 12 is [2,2,3]. A prime that divides the number more than once
appears that many times. List the primes in increasing order. The number 1 has no prime factors, so its
list is empty.
Return one list for each number, in the same order as nums.
Example 1
Input: nums = [12, 7, 100]
[[2,2,3],[7],[2,2,5,5]]Explanation: 12 = 2 × 2 × 3 and 100 = 2 × 2 × 5 × 5. The number 7 is prime, so its list holds just 7.
Example 2
Input: nums = [1, 64]
[[],[2,2,2,2,2,2]]Explanation: 1 has no prime factors, so its list is empty. 64 is 2 multiplied by itself six times.
Example 3
Input: nums = [999983, 1000000, 999999]
[[999983],
[2,2,2,2,2,2,5,5,5,5,5,5],
[3,3,3,7,11,13,37]]Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 1051 ≤ nums[i] ≤ 106
Clarifying questions
What you would ask an interviewer before writing any code.