CODEWITHSUNDEEP
algorithmprimes
Appstarter
Appstarter

Reputation: 59

Algorithm for farthest coprime

Given an array of n numbers, replace each element with it’s farthest coprime in the range [2, 250]. Example, the farthest coprime for 2 is 249 and for 243 is 2.

Could anyone help me with algorithm with the best complexity yo solve this?

Upvotes: 0

Views: 7855

Answers (2)

user2736738
user2736738

Reputation: 30926

As the number range is small I would go for some application of sieve. 

for (int i = 2; i <= N; ++i)
{
    if (N % i == 0)
    {
        sieve[i] = 1;
        for (int j = 2; j * i <= 250; ++j)
        {
            sieve[i * j] = 1;
        }
    }
}

After that using this, you will look for smallest value sm for which sieve[sm] is 0 and also largest value lg for which sieve[lg] is 0. Then among them get from which the distance to N is maximum. That is your answer.

Sieve has the complexity of O(nloglogn). And the looping to find the farthest will be O(n). So overall complexity is O(nloglogn).

Logic behind this:

Simply we are marking the values that are not co-prime for this particular number N.

Then we just loop over to get the smallest and largest number which are coprime to the given number. We then calculate the distance and then make the largest one as the answer.

Upvotes: 2

Ralf Kleberhoff
Ralf Kleberhoff

Reputation: 7290

For the farthest coprime of N from the range [2, 250], the candidates are:

  • 250 is a candidate if N is not divisible by 2 or by 5.
  • 249 is a candidate. It's prime, so it's surely co-prime with all numbers below 249.
  • Final candidate is the first prime number that N is not divisible by (e.g. for N=240, that prime is 7). A list of prime numbers from 2 up to 250 need not be computed at run time, but can be spelled out as array initialization.

Of these (up to) three candidates, choose the one farthest from N.

Upvotes: 1

Related Questions