# Farthest Co-prime

• 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.

• ``````class solution
{
public int farthestprime(int num)
{
bool[] flag = new bool[251];
for (int i = 2; i <= num; ++i)
{
if (num % i == 0)
{
flag[i] = true;
for (int j = 2; j * i <= 250; ++j)
{
flag[i * j] = true;
}
}
}
int front = 2;
while(front<=250&&flag[front]==true){
front++;
}
int back=250;
while(back>=0&&flag[back]==true){
back--;
}
return (num-front)>(back-num)?front:back;
}
}
``````

• @tianjiao and then you'll invoke this method for each element in the input array?

• ``````        static void Main(string[] args)
{
var coPrimeStart = 2;
var coPrimeEnd = 250;
var list = new int[coPrimeEnd];

Console.WriteLine(Coprime(2, 249));

for (var i = coPrimeStart; i <= coPrimeEnd; i++)
{
list[i - 1] = GetFarthestCoPrime(i, coPrimeStart, coPrimeEnd);
}
}

public static int GetFarthestCoPrime(int number, int start, int end)
{
var leftMost = 0;
var rightMost = 0;

for (var i = start; i <= end; i++)
{
if (Coprime(i, number))
{
if (0 == leftMost)
{
leftMost = i;
}

rightMost = i;
}
}

if (rightMost - number > Math.Abs(leftMost - number))
{
return rightMost;
}

return leftMost;
}

public static int GetGCDByModulus(int value1, int value2)
{
while (value1 != 0 && value2 != 0)
{
if (value1 > value2)
value1 %= value2;
else
value2 %= value1;
}
return Math.Max(value1, value2);
}

public static bool Coprime(int value1, int value2)
{
return GetGCDByModulus(value1, value2) == 1;
}
``````

• ``````       public static int[] farthestCoprimes(int end) {
int[] out = new int[end - 1];
int k = 0;
for (int i = 2; i <= end; i++) {
// get coprime for each number
out[k] = getFarthestCoprime(i, end);
k++;
}

return out;
}

public static int getFarthestCoprime(int pivot, int end) {
int mid = end / 2;
int rightCoprime = 0, leftCoprime = 0;
// if pivot is greater than mid then check coprime in left half, else
// check coprime in right half
// find it in right half
if (pivot > mid) {
for (int i = 2; i < end; i++) {
if (isCoprime(pivot, i)) {
leftCoprime = i;
break;
}
}
} else {
for (int i = end; i >= 2; i--) {
if (isCoprime(pivot, i)) {
rightCoprime = i;
break;
}
}
}

if (leftCoprime > rightCoprime) {
return leftCoprime;
} else {
return rightCoprime;
}
}

public static boolean isCoprime(int i, int j) {
while (i != 0 && j != 0) {
if (i > j)
i %= j;
else
j %= i;
}
return Math.max(i, j) == 1;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.