PPractick

The problem

A cryptography teaching tool lets students type a number and shows its distinct prime factors in increasing order, for example 100 → 2, 5. Numbers go up to about 10⁹, so testing every candidate up to n is too slow. Trial division up to √n is enough: divide out each factor completely when you find it (which guarantees every factor found is prime), and whatever is left above 1 at the end must itself be a prime larger than √n.

Example: 100 → 2 5; 13 → 13.

Function signature

vector<long long> primeFactors(long long n);  // distinct primes, ascending; n >= 1

Test cases

Input	Output	Explanation
100	2 5	100 = 2² · 5²
35	5 7
13	13	A prime is its own only prime factor
1	(none)	1 has no prime factors
30030	2 3 5 7 11 13	The product of the first six primes
1000000007	1000000007	A large prime: the loop stops at √n

(Confirm: each prime is listed once, in increasing order; n ≤ about 10¹².)

How interviewers phrase it

• "Given a number N, find its unique prime factors in increasing order" (GeeksforGeeks "Prime Factors").

Clarifying questions to ask

1. Distinct primes, or with multiplicity? (Distinct here.)
2. How large is N, and how many queries? (Large N and one query → trial division; many small queries → a sieve.)
3. What should N = 1 return?

Follow-ups to expect

1. "Why only up to √n?"
2. "Why is every recorded divisor prime?"
3. "Why must the check use the shrinking n?"
4. "How would you handle many queries?"
5. "Complexity?"

Related questions

• Count primes in range L to R Hard
• Prime factorisation of a Number 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