# 1. Problem Understanding We are given a number $n$, and our task is to compute the sum of all its unique prime divisors. If the prime factorization of $n$ is given by $$ n = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}, $$ we need to find the sum $$ S = p_1 + p_2 + \cdots + p_k. $$ An additional edge case is when $n = 1$, which has no prime divisors; in that case, the output should be $-1$. We need to handle up to $T$ test cases while each $n$ is bounded by $1 \leq n \leq 10^6$. # 2. Solution Analysis A straightforward approach is to factorize $n$ by checking for prime factors: - **For $n=1$:** Output $-1$ directly. - **Check for divisibility by 2:** Because 2 is the only even prime, if $n$ is divisible by 2, add 2 to the sum and repeatedly divide $n$ by 2 until it is no longer even. - **Check for odd factors:** Iterate over odd integers from 3 to $\sqrt{n}$. For each odd number $i$, if $i$ divides $n$, then it is a prime divisor. Add $i$ to the sum and repeatedly divide $n$ by $i$ until it no longer divides $n$. - **Remaining number:** After processing factors up to $\sqrt{n}$, if $n$ is greater than 1, then the remaining $n$ must be a prime divisor. Add it to the sum. An alternative approach, to improve efficiency for many test cases, is to precompute the smallest prime factor (SPF) for every number up to $10^6$ using a sieve technique. Then for each test case, use the SPF table to quickly factorize $n$ and sum the unique prime divisors by repeatedly dividing $n$ by its SPF. # 3. Time and Space Complexity Analysis - **Trial Division Approach:** - *Time Complexity:* In the worst-case scenario (when $n$ is a prime or has large prime factors), checking divisibility up to $\sqrt{n}$ takes up to $O(\sqrt{n})$. As $n \leq 10^6$, this is roughly $O(10^3)$ per test case. Given that there can be up to $10^5$ test cases, the overall complexity comes to $O(10^5 \times 10^3)$, which is acceptable in many competitive programming environments in languages like C++ with optimized code. - *Space Complexity:* $O(1)$ extra space per test case. - **Precomputation with SPF Approach:** - *Time Complexity:* - The sieve for computing SPF for all numbers up to $10^6$ runs in $O(n \log \log n)$. - Factorizing each $n$ using the SPF table typically takes $O(\log n)$ time per test case. - *Space Complexity:* The SPF table requires $O(10^6)$ space.