Divisor Cutter (Editorial)

Let $f(x)$ be the maximum proper divisor of $x$. We want to partition $n$ into n_1 + n_2 + \dots + n_k (n_i > 1) to minimize \sum f(n_i).

Notice that the maximum proper divisor f(x) = 1 if and only if $x$ is a prime number. For any composite number, f(x) \ge 2. Therefore, to minimize the waste, we should aim to split the log into the minimum possible number of prime parts.

This naturally leads to Goldbach's Conjecture, which states that every even integer greater than 2 can be expressed as the sum of two primes.

Based on this, we can define three cases for $n$:

1. $n$ is prime: We don't split the log at all. The waste is exactly $1$.

2. $n$ is even (and $>2$): By Goldbach's conjecture, $n$ can be split into exactly two prime numbers. The waste for each is $1$, making the total waste 1 + 1 = 2.

3. $n$ is odd (and composite): We can try to split $n$ into a prime and an even number. If we pull out $2$ (the only even prime), we are left with n-2.

   • If n-2 is also prime, we have split $n$ into two primes ($2$ and n-2). The waste is $2$.

   • If n-2 is composite, we cannot split $n$ into two primes. Instead, we pull out $3$, leaving the even number n-3. By Goldbach's conjecture, n-3 can be split into two primes. This gives us a total of three primes, making the waste $3$.

Complexity: O(\sqrt{n}) per test case for primality testing.