736B. Taxes

MathematicsNumber TheoryGoldbach’s Conjecture

Mr. Funt now lives in a country with a very specific tax laws. The total income of mr. Funt during this year is equal to n (n ≥ 2) burles and the amount of tax he has to pay is calculated as the maximum divisor of n (not equal to n, of course). For example, if n = 6 then Funt has to pay 3 burles, while for n = 25 he needs to pay 5 and if n = 2 he pays only 1 burle.

As Mr. Funt is a very opportunistic person he wants to cheat a bit. In particular, he wants to split the initial n in several parts n₁ + n₂ + … + n_k = n (here k is arbitrary, even k = 1 is allowed) and pay the taxes for each part separately. He can’t make some part equal to 1 because it will reveal him. So, the condition ni ≥ 2 should hold for all i from 1 to k.

Ostap Bender wonders, how many money Funt has to pay (i.e. minimal) if he chooses and optimal way to split n in parts.

Hints

Hint 1

Goldbach’s Conjecture states every even number greater than 2 can be represented as the sum of two primes.

Hint 2

An odd number cannot be the sum of two other odd numbers.

Hint 3

2 is the only even prime number. Hence, there’s only a single way an odd number can be a sum of two primes.

Solution

One can come to a conclusion easily that the tax becomes minimal when we represent Mr. Funt’s income as the sum of the largest possible primes. Primes, as with the maximal divisor as 1, stand as the best in for tax minimisation.

Hence, if the input is prime, the output is 1. How to check if a number is prime?

if (isprime(n)) cout << 1;

Goldbach’s conjecture states all even numbers greater than 2 can be represented as the sum of primes. Hence, any even number input other than 2 can produce an output of 2. [Read about Goldbach’s conjecture]

if (n%2 == 0) cout << 2;

For all other numbers (odd), we can check if they can be represented as the sum of two primes - true only if (n - 2) is prime, as an odd number can only be represented as the sum of an odd and another even number, with 2 as the only even prime.

else if (isprime(n - 2)) cout << 2;

All other odd numbers can be considered as the sum of 3 primes - 3 and the two primes that constitute the even number, (n - 3).

Code

include<bits/stdc++.h>
using namespace std;

#define ll long long
#define f(i, start, count) for (i = start;i < count;i++)

int isprime(ll int n) {
    ll int i, s = sqrt(n);
    f(i, 2, s + 1) if (n%i == 0) return 0;
    return 1;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll int n;
    cin >> n;
    //cases where 1
    if (n == 2) cout << 1;
    else if (isprime(n)) cout << 1;
    //cases where 2
    else if (n%2 == 0) cout << 2;
    else if (isprime(n - 2)) cout << 2;
    //case where 3
    else cout << 3;

    return 0;
}

Written by Nandakishore