Encontrar un triplete coprimo no transitivo en un rango

Dados L y R, encuentre un posible triplete no transitivo (a, b, c) tal que el par (a, b) sea coprimo y el par (b, c) sea coprimo pero (a, c) no lo sea co-principal 
Por ejemplo: (2, 5, 6) es un triplete no transitivo ya que el par (2, 5) es coprimo y el par (5, 6) es coprimo pero el par (2, 6) no es coprimo.

Ejemplos:  

Entrada: L = 2, R = 10 
Salida: a = 4, b = 7, c = 8 es uno de esos tripletes 
Explicación (4, 7, 8) es un posible triplete (mientras que hay otros tales tripletes presentes en este rango) , Aquí, el par (4, 7) es coprimo y el par (7, 8) es coprimo pero el par (4, 8) no es coprimo
Entrada: L = 21, R = 47 
Salida: a = 23, b = 25, c = 46 es uno de esos tripletes 
Explicación (23, 25, 46) es un posible triplete (mientras que hay otros tales tripletes presentes en este rango), Aquí, el par (23, 25) es coprimo y el par (25, 46) es coprimo pero el par (23, 46) no es coprimo 

                                                                      Método 1 (Fuerza bruta):

Generamos todos los trillizos posibles entre L y R y verificamos si la propiedad es cierta de que el par (a, b) es coprimo y el par (b, c) es coprimo pero el par (a, c) no lo es. 
 

C++

// C++ program to find possible non transitive triplets btw L and R
#include <bits/stdc++.h>
using namespace std;
 
// Function to return gcd of a and b
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
 
// function to check for gcd
bool coprime(int a, int b)
{
    // a and b are coprime if their gcd is 1.
    return (gcd(a, b) == 1);
}
 
/* Checks if any possible triplet (a, b, c) satisfying the condition
   that (a, b) is coprime, (b, c) is coprime but (a, c) isnt */
void possibleTripletInRange(int L, int R)
{
 
    bool flag = false;
    int possibleA, possibleB, possibleC;
 
    // Generate and check for all possible triplets
    // between L and R
    for (int a = L; a <= R; a++) {
        for (int b = a + 1; b <= R; b++) {
            for (int c = b + 1; c <= R; c++) {
 
                // if we find any such triplets set flag to true
                if (coprime(a, b) && coprime(b, c) && !coprime(a, c)) {
                    flag = true;
                    possibleA = a;
                    possibleB = b;
                    possibleC = c;
                    break;
                }
            }
        }
    }
 
    // flag = True indicates that a pair exists
    // between L and R
    if (flag == true) {
        cout << "(" << possibleA << ", " << possibleB
             << ", " << possibleC << ")"
             << " is one such possible triplet between "
             << L << " and " << R << "\n";
    }
    else {
        cout << "No Such Triplet exists between "
             << L << " and " << R << "\n";
    }
}
 
// Driver code
int main()
{
    int L, R;
 
    // finding possible Triplet between 2 and 10
    L = 2;
    R = 10;
    possibleTripletInRange(L, R);
 
    // finding possible Triplet between 23 and 46
    L = 23;
    R = 46;
    possibleTripletInRange(L, R);
 
    return 0;
}

Java

// Java program to find possible non
// transitive triplets btw L and R
class GFG {
     
    // Function to return gcd of a and b
    static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
             
        return gcd(b % a, a);
    }
 
    // function to check for gcd
    static boolean coprime(int a, int b)
    {
         
        // a and b are coprime if their
        // gcd is 1.
        return (gcd(a, b) == 1);
    }
 
    // Checks if any possible triplet
    // (a, b, c) satifying the condition
    // that (a, b) is coprime, (b, c) is
    // coprime but (a, c) isnt */
    static void possibleTripletInRange(int L, int R)
    {
 
        boolean flag = false;
        int possibleA = 0, possibleB = 0,
                           possibleC = 0;
 
        // Generate and check for all possible
        // triplets between L and R
        for (int a = L; a <= R; a++) {
            for (int b = a + 1; b <= R; b++) {
                for (int c = b + 1; c <= R; c++)
                {
 
                    // if we find any such triplets
                    // set flag to true
                    if (coprime(a, b) && coprime(b, c)
                                    && !coprime(a, c))
                    {
                        flag = true;
                        possibleA = a;
                        possibleB = b;
                        possibleC = c;
                        break;
                    }
                }
            }
        }
 
        // flag = True indicates that a pair exists
        // between L and R
        if (flag == true) {
            System.out.println("(" + possibleA + ", "
                  + possibleB + ", " + possibleC + ")"
                    + " is one such possible triplet "
                      + "between " + L + " and " + R);
        }
        else {
            System.out.println("No Such Triplet exists"
                      + "between " + L + " and " + R);
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
         
        int L, R;
 
        // finding possible Triplet between
        // 2 and 10
        L = 2;
        R = 10;
        possibleTripletInRange(L, R);
 
        // finding possible Triplet between
        // 23 and 46
        L = 23;
        R = 46;
        possibleTripletInRange(L, R);
    }
}
 
// This code is contributed by
// Smitha DInesh Semwal

Python3

# Python3 program to find possible non
# transitive triplets btw L and R
 
# Function to return gcd of a and b
def gcd(a, b):
 
    if (a == 0):
        return b;
    return gcd(b % a, a);
 
# function to check for gcd
def coprime(a, b):
 
    # a and b are coprime if
    # their gcd is 1.
    return (gcd(a, b) == 1);
 
# Checks if any possible triplet
# (a, b, c) satifying the condition
# that (a, b) is coprime, (b, c)
# is coprime but (a, c) isnt
def possibleTripletInRange(L, R):
 
    flag = False;
    possibleA = 0;
    possibleB = 0;
    possibleC = 0;
 
    # Generate and check for all
    # possible triplets between L and R
    for a in range(L, R + 1):
        for b in range(a + 1, R + 1):
            for c in range(b + 1, R + 1):
                 
                # if we find any such triplets
                # set flag to true
                if (coprime(a, b) and coprime(b, c) and    
                                      coprime(a, c) == False):
                    flag = True;
                    possibleA = a;
                    possibleB = b;
                    possibleC = c;
                    break;
 
    # flag = True indicates that a
    # pair exists between L and R
    if (flag == True):
        print("(", possibleA, ",", possibleB,
              ",", possibleC, ") is one such",
              "possible triplet between", L, "and", R);
    else:
        print("No Such Triplet exists between",
                                  L, "and", R);
 
# Driver Code
 
# finding possible Triplet
# between 2 and 10
L = 2;
R = 10;
possibleTripletInRange(L, R);
 
# finding possible Triplet
# between 23 and 46
L = 23;
R = 46;
possibleTripletInRange(L, R);
 
# This code is contributed by mits

C#

// C# program to find possible
// non transitive triplets
// btw L and R
using System;
class GFG
{
    // Function to return
    // gcd of a and b
    static int gcd(int a,
                   int b)
    {
        if (a == 0)
            return b;
             
        return gcd(b % a, a);
    }
 
    // function to
    // check for gcd
    static bool coprime(int a,
                        int b)
    {
         
        // a and b are coprime
        // if their gcd is 1.
        return (gcd(a, b) == 1);
    }
 
    // Checks if any possible
    // triplet (a, b, c) satifying
    // the condition that (a, b)
    // is coprime, (b, c) is
    // coprime but (a, c) isnt */
    static void possibleTripletInRange(int L,
                                       int R)
    {
 
        bool flag = false;
        int possibleA = 0,
            possibleB = 0,
            possibleC = 0;
 
        // Generate and check for
        // all possible triplets
        // between L and R
        for (int a = L; a <= R; a++)
        {
            for (int b = a + 1;
                     b <= R; b++)
            {
                for (int c = b + 1;
                         c <= R; c++)
                {
 
                    // if we find any
                    // such triplets
                    // set flag to true
                    if (coprime(a, b) &&
                        coprime(b, c) &&
                       !coprime(a, c))
                    {
                        flag = true;
                        possibleA = a;
                        possibleB = b;
                        possibleC = c;
                        break;
                    }
                }
            }
        }
 
        // flag = True indicates
        // that a pair exists
        // between L and R
        if (flag == true)
        {
            Console.WriteLine("(" + possibleA + ", " +
                                    possibleB + ", " +
                                    possibleC + ")" +
                    " is one such possible triplet " +
                        "between " + L + " and " + R);
        }
        else
        {
            Console.WriteLine("No Such Triplet exists" +
                          "between " + L + " and " + R);
        }
    }
 
    // Driver code
    public static void Main()
    {
        int L, R;
 
        // finding possible
        // Triplet between
        // 2 and 10
        L = 2;
        R = 10;
        possibleTripletInRange(L, R);
 
        // finding possible
        // Triplet between
        // 23 and 46
        L = 23;
        R = 46;
        possibleTripletInRange(L, R);
    }
}
 
// This code is contributed
// by anuj_67.

PHP

<?php
// PHP program to find possible non
// transitive triplets btw L and R
 
// Function to return gcd of a and b
function gcd($a, $b)
{
    if ($a == 0)
        return $b;
    return gcd($b % $a, $a);
}
 
// function to check for gcd
function coprime($a, $b)
{
    // a and b are coprime if
    // their gcd is 1.
    return (gcd($a, $b) == 1);
}
 
/* Checks if any possible triplet
   (a, b, c) satifying the condition
   that (a, b) is coprime, (b, c)
   is coprime but (a, c) isnt */
function possibleTripletInRange($L, $R)
{
    $flag = false;
    $possibleA;
    $possibleB;
    $possibleC;
 
    // Generate and check for all
    // possible triplets between L and R
    for ($a = $L; $a <= $R; $a++)
    {
        for ($b = $a + 1; $b <= $R; $b++)
        {
            for ( $c = $b + 1; $c <= $R; $c++)
            {
 
                // if we find any such triplets
                // set flag to true
                if (coprime($a, $b) &&
                    coprime($b, $c) &&
                   !coprime($a, $c))
                {
                    $flag = true;
                    $possibleA = $a;
                    $possibleB = $b;
                    $possibleC = $c;
                    break;
                }
            }
        }
    }
 
    // flag = True indicates that a
    // pair exists between L and R
    if ($flag == true)
    {
        echo "(" ,$possibleA ,
             ", " , $possibleB,
             ", " , $possibleC , ")",
             " is one such possible triplet between ",
               $L , " and " , $R , "\n";
    }
    else
    {
        echo "No Such Triplet exists between ",
                      $L , " and " , $R , "\n";
    }
}
 
// Driver Code
$L;
$R;
 
// finding possible Triplet
// between 2 and 10
$L = 2;
$R = 10;
possibleTripletInRange($L, $R);
 
// finding possible Triplet
// between 23 and 46
$L = 23;
$R = 46;
possibleTripletInRange($L, $R);
 
// This code is contributed by jit_t
?>

Javascript

<script>
 
    // Javascript program to find possible
    // non transitive triplets
    // btw L and R
     
    // Function to return
    // gcd of a and b
    function gcd(a, b)
    {
        if (a == 0)
            return b;
               
        return gcd(b % a, a);
    }
   
    // function to
    // check for gcd
    function coprime(a, b)
    {
           
        // a and b are coprime
        // if their gcd is 1.
        return (gcd(a, b) == 1);
    }
   
    // Checks if any possible
    // triplet (a, b, c) satifying
    // the condition that (a, b)
    // is coprime, (b, c) is
    // coprime but (a, c) isnt */
    function possibleTripletInRange(L, R)
    {
   
        let flag = false;
        let possibleA = 0,
            possibleB = 0,
            possibleC = 0;
   
        // Generate and check for
        // all possible triplets
        // between L and R
        for (let a = L; a <= R; a++)
        {
            for (let b = a + 1;
                     b <= R; b++)
            {
                for (let c = b + 1;
                         c <= R; c++)
                {
   
                    // if we find any
                    // such triplets
                    // set flag to true
                    if (coprime(a, b) &&
                        coprime(b, c) &&
                       !coprime(a, c))
                    {
                        flag = true;
                        possibleA = a;
                        possibleB = b;
                        possibleC = c;
                        break;
                    }
                }
            }
        }
   
        // flag = True indicates
        // that a pair exists
        // between L and R
        if (flag == true)
        {
            document.write("(" + possibleA + ", " +
                              possibleB + ", " +
                         possibleC + ")" +
             " is one such possible triplet " +
              "between " + L + " and " + R + "</br>");
        }
        else
        {
            document.write("No Such Triplet exists" +
             "between " + L + " and " + R + "</br>");
        }
    }
     
    let L, R;
   
    // finding possible
    // Triplet between
    // 2 and 10
    L = 2;
    R = 10;
    possibleTripletInRange(L, R);
 
    // finding possible
    // Triplet between
    // 23 and 46
    L = 23;
    R = 46;
    possibleTripletInRange(L, R);
     
</script>

Producción:  

(8, 9, 10) is one such possible triplet between 2 and 10
(44, 45, 46) is one such possible triplet between 23 and 46

La complejidad temporal de la solución de fuerza bruta es O(n 3 log(A)) donde A es el número más pequeño del triplete. 
Nota : El factor logarítmico de la complejidad es el de calcular el GCD para un par de números.
 

                                                              Método 2 (eficiente) :

Dado que solo necesitamos uno de esos pares posibles, podemos usar esto para desglosar aún más nuestra complejidad.
Solo necesitamos identificar algunos casos y buscar resolverlos para resolver este problema.
Caso 1: Hay menos de 3 números entre L y R. 
Este caso es fácil, no podemos formar ningún triplete, por lo que la respuesta es que este caso siempre sería ‘No posible’
Caso 2: Hay más de tres números entre L y R. 
Ahora, 
es una prueba bien conocida de que los números consecutivos siempre son coprimos. Incluso podemos probar esto fácilmente. 

Proof:
Given that N and N + 1 are two consecutive integers. 
Now suppose gcd(n, n + 1) = X,
? X divides n and X also divides (n + 1). 
Which implies that X divides ((n + 1) - n) or X divides 1.
But, There is no number which divides 1 except 1.
? X = 1, or we can also say that gcd(n, n + 1) = 1 

Thus, n and n + 1 are coprime.

Entonces, si tomamos tres números consecutivos de la forma 2k, 2k + 1, 2k + 2, siempre terminaríamos teniendo un triplete posible porque, como se demostró anteriormente, los pares (2k, 2k + 1) y (2k + 1, 2k + 2) al ser pares de números consecutivos son coprimos y el par (2k, 2k+2) tienen su mcd 2 (ya que son pares).
Caso 3: Cuando hay exactamente 3 números entre L y R 
Esta es una extensión del caso 3, ahora este caso puede tener 2 casos,
Caso 3.1 Cuando los tres números son de la forma 2k, 2k + 1, 2k + 2 
Tenemos Ya vimos este caso en el caso 2. Así que este es el único triplete y también es un triplete válido entre L y R.
Caso 3.2 Cuando los tres números son de la forma 2k – 1, 2k, 2k + 1 
Ya hemos visto que (2k – 1, 2k) y (2k, 2k + 1) siendo un par de números consecutivos son pares coprimos, por lo que debemos comprobar si el par (2k – 1, 2k + 1) es coprimos o no 
Se puede demostrar que el par (2k – 1, 2k + 1) siempre es coprimo como se muestra a continuación 

Proof:
Given that 2k - 1 and 2k + 1 are two numbers 
Now suppose gcd((2k - 1), (2k + 1)) = X,
? X divides (2k - 1) and X also divides (2k + 1). 
Which implies that X divides ((2k + 1) - (2k - 1)) or X divides 2.
2 being a prime is only divisible by 1 and 2 itself. 
But, 2k - 1 and 2k + 1 are odd numbers so X can never be equal to 2.
? X = 1, or we can also say that gcd((2k -1), (2k + 1)) = 1 

Thus, 2k - 1 and 2k + 1 are coprime.

Así, en este caso, no podremos encontrar ningún posible triplete válido.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

/* C++ program to find a non transitive co-prime
   triplets between L and R */
#include <bits/stdc++.h>
using namespace std;
 
/* Checks if any possible triplet (a, b, c) satisfying the condition
   that (a, b) is coprime, (b, c) is coprime but (a, c) isnt */
 
void possibleTripletInRange(int L, int R)
{
 
    bool flag = false;
    int possibleA, possibleB, possibleC;
 
    int numbersInRange = (R - L + 1);
 
    /* Case 1 : Less than 3 numbers between L and R */
    if (numbersInRange < 3) {
        flag = false;
    }
 
    /* Case 2: More than 3 numbers between L and R */
    else if (numbersInRange > 3) {
        flag = true;
 
        // triplets should always be of form (2k, 2k + 1, 2k + 2)
        if (L % 2) {
            L++;
        }
 
        possibleA = L;
        possibleB = L + 1;
        possibleC = L + 2;
    }
 
    else {
        /* Case 3.1: Exactly 3 numbers in range of form
                     (2k, 2k + 1, 2k + 2) */
        if (!(L % 2)) {
            flag = true;
            possibleA = L;
            possibleB = L + 1;
            possibleC = L + 2;
        }
        else {
            /* Case 3.2: Exactly 3 numbers in range of form
                         (2k - 1, 2k, 2k + 1) */
            flag = false;
        }
    }
 
    // flag = True indicates that a pair exists between L and R
    if (flag == true) {
        cout << "(" << possibleA << ", " << possibleB
             << ", " << possibleC << ")"
             << " is one such possible triplet between "
             << L << " and " << R << "\n";
    }
    else {
        cout << "No Such Triplet exists between "
             << L << " and " << R << "\n";
    }
}
 
// Driver code
int main()
{
    int L, R;
 
    // finding possible Triplet between 2 and 10
    L = 2;
    R = 10;
    possibleTripletInRange(L, R);
 
    // finding possible Triplet between 23 and 46
    L = 23;
    R = 46;
    possibleTripletInRange(L, R);
 
    return 0;
}

Java

// Java program to find a
// non transitive co-prime
// triplets between L and R
import java.io.*;
 
class GFG
{
 
// Checks if any possible triplet
// (a, b, c) satifying the condition
// that (a, b) is coprime, (b, c)
// is coprime but (a, c) isnt
static void possibleTripletInRange(int L,
                                   int R)
{
    boolean flag = false;
    int possibleA = 0,
        possibleB = 0,
        possibleC = 0;
  
    int numbersInRange = (R - L + 1);
 
    // Case 1 : Less than 3
    // numbers between L and R
    if (numbersInRange < 3)
    {
        flag = false;
    }
 
    // Case 2: More than 3
    // numbers between L and R
    else if (numbersInRange > 3)
    {
        flag = true;
 
        // triplets should always
        // be of form (2k, 2k + 1,
        // 2k + 2)
        if (L % 2 > 0)
        {
            L++;
        }
 
        possibleA = L;
        possibleB = L + 1;
        possibleC = L + 2;
    }
 
    else
    {
        /* Case 3.1: Exactly 3 numbers
                      in range of form
                     (2k, 2k + 1, 2k + 2) */
        if (!(L % 2 > 0))
        {
            flag = true;
            possibleA = L;
            possibleB = L + 1;
            possibleC = L + 2;
        }
        else
        {
            /* Case 3.2: Exactly 3 numbers
                         in range of form
                         (2k - 1, 2k, 2k + 1) */
            flag = false;
        }
    }
 
    // flag = True indicates
    // that a pair exists
    // between L and R
    if (flag == true)
    {
        System.out.println("(" + possibleA +
                          ", " + possibleB +
                          ", " + possibleC +
             ")" + " is one such possible" +
                       " triplet between " +
                          L + " and " + R );
    }
    else {
        System.out.println("No Such Triplet" +
                          " exists between " +
                             L + " and " + R);
    }
}
 
// Driver code
public static void main (String[] args)
{
int L, R;
 
// finding possible Triplet
// between 2 and 10
L = 2;
R = 10;
possibleTripletInRange(L, R);
 
// finding possible Triplet
// between 23 and 46
L = 23;
R = 46;
possibleTripletInRange(L, R);
}
}
 
// This code is contributed
// by anuj_67.

Python3

# Python3 program to find a non transitive
# co-prime triplets between L and R
 
# Checks if any possible triplet (a, b, c)
# satifying the condition that (a, b) is
# coprime, (b, c) is coprime but (a, c) isnt
def possibleTripletInRange(L, R):
 
    flag = False;
    possibleA = 0;
    possibleB = 0;
    possibleC = 0;
 
    numbersInRange = (R - L + 1);
 
    # Case 1 : Less than 3 numbers
    # between L and R
    if (numbersInRange < 3):
        flag = False;
 
    # Case 2: More than 3 numbers
    # between L and R
    elif (numbersInRange > 3):
        flag = True;
 
        # triplets should always be of
        # form (2k, 2k + 1, 2k + 2)
        if ((L % 2) > 0):
            L += 1;
 
        possibleA = L;
        possibleB = L + 1;
        possibleC = L + 2;
 
    else:
         
        # Case 3.1: Exactly 3 numbers in range
        #            of form (2k, 2k + 1, 2k + 2)
        if ((L % 2) == 0):
            flag = True;
            possibleA = L;
            possibleB = L + 1;
            possibleC = L + 2;
        else:
             
            # Case 3.2: Exactly 3 numbers in range
            #            of form (2k - 1, 2k, 2k + 1)
            flag = False;
 
    # flag = True indicates that a pair
    # exists between L and R
    if (flag == True):
        print("(", possibleA, ",", possibleB,
              ",", possibleC, ") is one such",
              "possible triplet between", L, "and", R);
    else:
        print("No Such Triplet exists between",
                                  L, "and", R);
 
# Driver code
 
# finding possible Triplet
# between 2 and 10
L = 2;
R = 10;
possibleTripletInRange(L, R);
 
# finding possible Triplet
# between 23 and 46
L = 23;
R = 46;
possibleTripletInRange(L, R);
 
# This code is contributed by mits

C#

// C#  program to find a
// non transitive co-prime
// triplets between L and R
using System;
 
public class GFG{
     
     
// Checks if any possible triplet
// (a, b, c) satifying the condition
// that (a, b) is coprime, (b, c)
// is coprime but (a, c) isnt
static void possibleTripletInRange(int L,
                                int R)
{
    bool flag = false;
    int possibleA = 0,
        possibleB = 0,
        possibleC = 0;
 
    int numbersInRange = (R - L + 1);
 
    // Case 1 : Less than 3
    // numbers between L and R
    if (numbersInRange < 3)
    {
        flag = false;
    }
 
    // Case 2: More than 3
    // numbers between L and R
    else if (numbersInRange > 3)
    {
        flag = true;
 
        // triplets should always
        // be of form (2k, 2k + 1,
        // 2k + 2)
        if (L % 2 > 0)
        {
            L++;
        }
 
        possibleA = L;
        possibleB = L + 1;
        possibleC = L + 2;
    }
 
    else
    {
        /* Case 3.1: Exactly 3 numbers
                    in range of form
                    (2k, 2k + 1, 2k + 2) */
        if (!(L % 2 > 0))
        {
            flag = true;
            possibleA = L;
            possibleB = L + 1;
            possibleC = L + 2;
        }
        else
        {
            /* Case 3.2: Exactly 3 numbers
                        in range of form
                        (2k - 1, 2k, 2k + 1) */
            flag = false;
        }
    }
 
    // flag = True indicates
    // that a pair exists
    // between L and R
    if (flag == true)
    {
            Console.WriteLine("(" + possibleA +
                        ", " + possibleB +
                        ", " + possibleC +
            ")" + " is one such possible" +
                    " triplet between " +
                        L + " and " + R );
    }
    else {
        Console.WriteLine("No Such Triplet" +
                        " exists between " +
                            L + " and " + R);
    }
}
 
// Driver code
     
static public void Main (){
     
    int L, R;
    // finding possible Triplet
    // between 2 and 10
    L = 2;
    R = 10;
    possibleTripletInRange(L, R);
    // finding possible Triplet
    // between 23 and 46
    L = 23;
    R = 46;
    possibleTripletInRange(L, R);
    }
}
// This code is contributed by ajit

PHP

<?php
// PHP program to find possible
// non transitive triplets
// btw L and R
function gcd($a, $b)
{
    if ($a == 0)
        return $b;
    return gcd($b % $a, $a);
}
 
// function to check for gcd
function coprime($a, $b)
{
    // a and b are coprime
    // if their gcd is 1.
    return (gcd($a, $b) == 1);
}
 
/* Checks if any possible triplet
(a, b, c) satifying the condition
that (a, b) is coprime, (b, c) is
coprime but (a, c) isnt */
function possibleTripletInRange($L, $R)
{
 
    $flag = false;
    $possibleA;
    $possibleB;
    $possibleC;
 
    // Generate and check for
    // all possible triplets
    // between L and R
    for ($a = $L; $a <= $R; $a++)
    {
        for ($b = $a + 1; $b <= $R; $b++)
        {
            for ($c = $b + 1; $c <= $R; $c++)
            {
 
                // if we find any such
                // triplets set flag to true
                if (coprime($a, $b) &&
                    coprime($b, $c) &&
                    !coprime($a, $c))
                {
                    $flag = true;
                    $possibleA = $a;
                    $possibleB = $b;
                    $possibleC = $c;
                    break;
                }
            }
        }
    }
 
    // flag = True indicates
    // that a pair exists
    // between L and R
    if ($flag == true)
    {
        echo "(" , $possibleA ,
            ", " , $possibleB ,
            ", " , $possibleC ,
            ")" , " is one such possible ",
                  "triplet between " , $L ,
                       " and " , $R , "\n";
    }
    else
    {
        echo "No Such Triplet exists between ",
                      $L , " and " , $R , "\n";
    }
}
 
// Driver code
 
// finding possible Triplet
// between 2 and 10
$L = 2;
$R = 10;
possibleTripletInRange($L, $R);
 
// finding possible Triplet
// between 23 and 46
$L = 23;
$R = 46;
possibleTripletInRange($L, $R);
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

Javascript

<script>
    /* Javascript program to find a non transitive co-prime
   triplets between L and R */
    
   /* Checks if any possible triplet (a, b, c) satisfying the condition
   that (a, b) is coprime, (b, c) is coprime but (a, c) isnt */
   
  function possibleTripletInRange(L, R)
  {
 
    let flag = false;
    let possibleA, possibleB, possibleC;
 
    let numbersInRange = (R - L + 1);
 
    /* Case 1 : Less than 3 numbers between L and R */
    if (numbersInRange < 3) {
      flag = false;
    }
 
    /* Case 2: More than 3 numbers between L and R */
    else if (numbersInRange > 3) {
      flag = true;
 
      // triplets should always be of form (2k, 2k + 1, 2k + 2)
      if (L % 2) {
        L++;
      }
 
      possibleA = L;
      possibleB = L + 1;
      possibleC = L + 2;
    }
 
    else {
      /* Case 3.1: Exactly 3 numbers in range of form
                         (2k, 2k + 1, 2k + 2) */
      if (!(L % 2)) {
        flag = true;
        possibleA = L;
        possibleB = L + 1;
        possibleC = L + 2;
      }
      else {
        /* Case 3.2: Exactly 3 numbers in range of form
                             (2k - 1, 2k, 2k + 1) */
        flag = false;
      }
    }
 
    // flag = True indicates that a pair exists between L and R
    if (flag == true) {
      document.write("(" + possibleA + ", " + possibleB
      + ", " + possibleC + ")"
      + " is one such possible triplet between "
      + L + " and " + R + "</br>");
    }
    else {
      document.write("No Such Triplet exists between "
      + L + " and " + R + "</br>");
    }
  }
   
  let L, R;
   
  // finding possible Triplet between 2 and 10
  L = 2;
  R = 10;
  possibleTripletInRange(L, R);
 
  // finding possible Triplet between 23 and 46
  L = 23;
  R = 46;
  possibleTripletInRange(L, R);
 
</script>

Producción:  

(2, 3, 4) is one such possible triplet between 2 and 10
(24, 25, 26) is one such possible triplet between 24 and 46

La complejidad temporal de este método es O(1).
 

Publicación traducida automáticamente

Artículo escrito por sirjan13 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *