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.