Encuentre tres números enteros menores o iguales a N tales que su MCM sea máximo

Dado un número N(>=3). La tarea es encontrar los tres enteros (<=N) tales que el LCM de estos tres enteros sea máximo. 
Ejemplos: 
 

Input: N = 3
Output: 1 2 3

Input: N = 5
Output: 3 4 5

Enfoque: Dado que la tarea es maximizar el MCM, si los tres números no tienen ningún factor común, el MCM será el producto de esos tres números y será máximo.
 

• Si n es impar, la respuesta será n, n-1, n-2 .
• Si n es par, 
  1. Si mcd de n y n-3 es 1, la respuesta será n, n-1, n-3 .
  2. De lo contrario, se requerirá respuesta n-1, n-2, n-3 .

A continuación se muestra la implementación del enfoque anterior: 
 

// CPP Program to find three integers
// less than N whose LCM is maximum
#include <bits/stdc++.h>
using namespace std;
 
// function to find three integers
// less than N whose LCM is maximum
void MaxLCM(int n)
{
    // if n is odd
    if (n % 2 != 0)
        cout << n << " " << (n - 1) << " " << (n - 2);
 
    // if n is even and n, n-3 gcd is 1
    else if (__gcd(n, (n - 3)) == 1)
        cout << n << " " << (n - 1) << " " << (n - 3);
 
    else
        cout << (n - 1) << " " << (n - 2) << " " << (n - 3);
}
 
// Driver code
int main()
{
    int n = 12;
 
    // function call
    MaxLCM(n);
 
    return 0;
}

// Java Program to find three integers
// less than N whose LCM is maximum
 
import java.io.*;
 
class GFG {
   // Recursive function to return gcd of a and b
static int __gcd(int a, int b)
{
    // Everything divides 0 
    if (a == 0)
       return b;
    if (b == 0)
       return a;
    
    // base case
    if (a == b)
        return a;
    
    // a is greater
    if (a > b)
        return __gcd(a-b, b);
    return __gcd(a, b-a);
}
 
// function to find three integers
// less than N whose LCM is maximum
static void MaxLCM(int n)
{
    // if n is odd
    if (n % 2 != 0)
        System.out.print(n + " " + (n - 1) + " " + (n - 2));
 
    // if n is even and n, n-3 gcd is 1
    else if (__gcd(n, (n - 3)) == 1)
        System.out.print( n + " " +(n - 1)+ " " + (n - 3));
 
    else
        System.out.print((n - 1) + " " + (n - 2) + " " + (n - 3));
}
 
// Driver code
public static void main (String[] args) {
    int n = 12;
 
    // function call
    MaxLCM(n);
    }
}
// This code is contributed by anuj_67..

# Python 3 Program to find three integers
# less than N whose LCM is maximum
from math import gcd
 
# function to find three integers
# less than N whose LCM is maximum
def MaxLCM(n) :
 
    # if n is odd
    if (n % 2 != 0) :
        print(n, (n - 1), (n - 2))
 
    # if n is even and n, n-3 gcd is 1
    elif (gcd(n, (n - 3)) == 1) :
        print(n, (n - 1), (n - 3))
 
    else :
        print((n - 1), (n - 2), (n - 3))
 
# Driver Code
if __name__ == "__main__" :
     
    n = 12
 
    # function call
    MaxLCM(n)
 
# This code is contributed by Ryuga

// C# Program to find three integers
// less than N whose LCM is maximum
 
using System;
 
class GFG {
// Recursive function to return gcd of a and b
static int __gcd(int a, int b)
{
    // Everything divides 0
    if (a == 0)
    return b;
    if (b == 0)
    return a;
     
    // base case
    if (a == b)
        return a;
     
    // a is greater
    if (a > b)
        return __gcd(a-b, b);
    return __gcd(a, b-a);
}
 
// function to find three integers
// less than N whose LCM is maximum
static void MaxLCM(int n)
{
    // if n is odd
    if (n % 2 != 0)
        Console.Write(n + " " + (n - 1) + " " + (n - 2));
 
    // if n is even and n, n-3 gcd is 1
    else if (__gcd(n, (n - 3)) == 1)
        Console.Write( n + " " +(n - 1)+ " " + (n - 3));
 
    else
        Console.Write((n - 1) + " " + (n - 2) + " " + (n - 3));
}
 
// Driver code
public static void Main () {
    int n = 12;
 
    // function call
    MaxLCM(n);
    }
}
// This code is contributed by anuj_67..

<?php
// PHP Program to find three integers
// less than N whose LCM is maximum
 
// Recursive function to return
// gcd of a and b
function __gcd($a, $b)
{
    // Everything divides 0
    if ($a == 0)
        return $b;
    if ($b == 0)
        return $a;
     
    // base case
    if ($a == $b)
        return $a;
     
    // a is greater
    if ($a > $b)
        return __gcd($a - $b, $b);
    return __gcd($a, $b - $a);
} 
 
// function to find three integers
// less than N whose LCM is maximum
function MaxLCM($n)
{
    // if n is odd
    if ($n % 2 != 0)
        echo $n , " " , ($n - 1) ,
                  " " , ($n - 2);
 
    // if n is even and n, n-3 gcd is 1
    else if (__gcd($n, ($n - 3)) == 1)
        echo $n , " " , ($n - 1),
                  " " , ($n - 3);
  
    else
        echo ($n - 1) , " " , ($n - 2),
                        " " , ($n - 3);
}
 
// Driver code
$n = 12;
 
// function call
MaxLCM($n);
 
// This code is contributed by Sachin
?>

<script>
 
// JavaScript Program to find three integers
// less than N whose LCM is maximum
 
    // Recursive function to return gcd of a and b
    function __gcd(a , b)
    {
        // Everything divides 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;
 
        // base case
        if (a == b)
            return a;
 
        // a is greater
        if (a > b)
            return __gcd(a - b, b);
        return __gcd(a, b - a);
    }
 
    // function to find three integers
    // less than N whose LCM is maximum
    function MaxLCM(n) {
        // if n is odd
        if (n % 2 != 0)
            document.write(n + " " + (n - 1) + " " + (n - 2));
 
        // if n is even and n, n-3 gcd is 1
        else if (__gcd(n, (n - 3)) == 1)
            document.write(n + " " + (n - 1) + " " + (n - 3));
 
        else
            document.write((n - 1) + " " + (n - 2) + " " + (n - 3));
    }
 
    // Driver code
     
        var n = 12;
 
        // function call
        MaxLCM(n);
         
// This code contributed by Rajput-Ji
 
</script>

11 10 9

Complejidad de tiempo: O(log(min(a, b))), donde a y b son dos parámetros de gcd.

Espacio auxiliar: O(log(min(a, b)))