PPractick

The problem

A number-theory API receives hundreds of thousands of requests, each asking for the full prime factorisation of a number up to 10⁶ (for example 60 → 2 2 3 5). Trial division per request costs O(√n) each time. Precompute, once, the smallest prime factor (SPF) of every number with a sieve. Then factorising n is just repeatedly dividing by spf[n], which takes O(log n) steps, since each division at least halves n.

Example: 60 → 2 2 3 5; 97 → 97.

Function signature

vector<int> buildSpf(int maxN);                        // spf[x] = smallest prime factor of x
vector<int> factorize(int n, const vector<int>& spf);  // primes with multiplicity, ascending

Test cases

Input	Output	Explanation
12	2 2 3
60	2 2 3 5
97	97	Prime: spf[97] = 97
1	(none)
1024	2 2 2 2 2 2 2 2 2 2	2¹⁰
999999	3 3 3 7 11 13 37

(Confirm: 1 ≤ n ≤ maxN (about 10⁶); factors are listed with multiplicity, in non-decreasing order.)

How interviewers phrase it

• "Given Q queries, print the prime factorisation of each number" (GeeksforGeeks "Prime Factorization using Sieve").

Clarifying questions to ask

1. With multiplicity (2 2 3) or distinct primes (2 3)?
2. What's the maximum value and the number of queries? (That decides between a sieve and trial division.)
3. What output format? (Ascending factors.)

Follow-ups to expect

1. "How is the SPF array built?"
2. "Why is each query O(log n)?"
3. "Why check spf[m] == m before writing?"
4. "Can SPF be computed in linear time?"
5. "Complexity?"

Related questions

• Print Prime Factors of a Number Hard
• Count primes in range L to R Hard
• Divisors of a Number Easy
• Count all Digits of a Number Easy
• Reverse a number Easy
• Palindrome Number Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in