Context: After reading the problem below, you might say there's a more optimal way to solve it. However, this note is meant to highlight a specific question: If you run a basic loop to solve this, will it actually get a TLE (Time Limit Exceeded) when given many test cases and no further restrictions?

Many beginners who don't know much about number theory might just brute-force it, and then wonder how their code actually passed. Let's see why.

Say you are given a number $$$n$$$ ($$$7 \le n \le 10^{18}$$$) and asked to find two distinct numbers $$$a$$$ and $$$b$$$ such that:

• $$$a + b = n$$$

• $$$\gcd(a,b) = 1$$$ (meaning $$$a$$$ and $$$b$$$ are coprimes)

• Important: Neither $$$a$$$ nor $$$b$$$ can be 1.

Because we are strictly not allowed to use 1, the obvious choice of setting $$$a = 1$$$ and $$$b = n - 1$$$ is gone.

So let's look at the math. As we know via the Euclidean property: $$$\gcd(a,b) = \gcd(a, a+b)$$$

Since $$$a + b = n$$$, we can rewrite this as: $$$\gcd(a,b) = \gcd(a, n)$$$

Thus, our task simplifies: we just have to find a number coprime to $$$n$$$ which is greater than 1 and less than $$$n-1$$$.

Now finding a coprime to a given number n we might think it may take O(n) to iterate a loop of i=2 to i=n-2 and say if test cases t <= $$$10^5$$$ and no further restrictions on n and t — we might think of it as high complexity method but in actual — does it take O(n) ?

Let's see

the worst case scenario we fear — loop is running and we haven't found a number coprime to it -> which means it has all prime factors(2,3,5,7....23,29,31,37...) till that

but

a number having all primes till 29 is at least = 2*3*5*.....23*29 which exceeds $$$10^9$$$

a number having all primes till 53 is at least = 2*3*5*.....23*29...43*47*53 which exceeds $$$10^{18}$$$

thus we can say

• if a loop runs till 47 and no coprime has been found :
  • we have 2 things guaranteed :
  • the number is near its limit $$$10^{18}$$$
  • the next prime 53 is coprime to n as if it isn't then it will exceed limit which isn't possible

• else a loop doesn't run successfully till 47 and we have found a number coprime to n earlier than 47 iterations

Thus it takes less than 60 iterations which is O(1)

and its safe to run a loop of i=2 to i=n-2 or even better run

const int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};

to find a coprime number to given number n

Reference question : 1617B - GCD Problem (though this question also has a better approach than this one)