Now finding a coprime to a given number n(<= $$$10^{18}$$$) we might think it may take O(n) to iterate a loop of i=2 to i=n-1 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-1 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)