Entero mínimo tal que deja un resto 1 al dividir con cualquier elemento del rango [2, N]

Dado un entero N , la tarea es encontrar el mínimo entero posible X tal que X % M = 1 para todos los M del rango [2, N]
Ejemplos: 

Entrada: N = 5 
Salida: 61 
61 % 2 = 1 
61 % 3 = 1 
61 % 4 = 1 
61 % 5 = 1
Entrada: N = 2 
Salida: 3  

Método: encuentra el mcm de todos los enteros del rango [2, N] y guárdalo en una variable lcm . Ahora sabemos que mcm es el número más pequeño que es divisible por todos los elementos del rango [2, N] y para que deje un resto de 1 en cada división, simplemente agregue 1 , es decir, mcm + 1 es la respuesta requerida .
A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the smallest number
// which on dividing with any element from
// the range [2, N] leaves a remainder of 1
long getMinNum(int N)
{
    // Find the LCM of the elements
    // from the range [2, N]
    int lcm = 1;
    for (int i = 2; i <= N; i++)
        lcm = ((i * lcm) / (__gcd(i, lcm)));
 
    // Return the required number
    return (lcm + 1);
}
 
// Driver code
int main()
{
    int N = 5;
 
    cout << getMinNum(N);
 
    return 0;
}

// Java implementation of the approach
class GFG {
 
    // Function to return the smallest number
    // which on dividing with any element from
    // the range [2, N] leaves a remainder of 1
    static long getMinNum(int N)
    {
        // Find the LCM of the elements
        // from the range [2, N]
        int lcm = 1;
        for (int i = 2; i <= N; i++)
            lcm = ((i * lcm) / (__gcd(i, lcm)));
 
        // Return the required number
        return (lcm + 1);
    }
 
    static int __gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return __gcd(b, a % b);
    }
 
    // Driver code
    public static void main(String args[])
    {
        int N = 5;
        System.out.println(getMinNum(N));
    }
}
 
// This code has been contributed by 29AjayKumar

# Python3 implementation of the approach
from math import gcd
 
# Function to return the smallest number
# which on dividing with any element from
# the range [2, N] leaves a remainder of 1
def getMinNum(N) :
 
    # Find the LCM of the elements
    # from the range [2, N]
    lcm = 1;
    for i in range(2, N + 1) :
        lcm = ((i * lcm) // (gcd(i, lcm)));
 
    # Return the required number
    return (lcm + 1);
 
 
# Driver code
if __name__ == "__main__" :
 
    N = 5;
 
    print(getMinNum(N));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG {
 
    // Function to return the smallest number
    // which on dividing with any element from
    // the range [2, N] leaves a remainder of 1
    static long getMinNum(int N)
    {
        // Find the LCM of the elements
        // from the range [2, N]
        int lcm = 1;
        for (int i = 2; i <= N; i++)
            lcm = ((i * lcm) / (__gcd(i, lcm)));
 
        // Return the required number
        return (lcm + 1);
    }
 
    static int __gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return __gcd(b, a % b);
    }
 
    // Driver code
    public static void Main()
    {
        int N = 5;
        Console.WriteLine(getMinNum(N));
    }
}
 
// This code has been contributed by anuj_67..

<?php
// PHP implementation of the approach
 
// Function to return the smallest number
// which on dividing with any element from
// the range [2, N] leaves a remainder of 1
function getMinNum($N)
{
    // Find the LCM of the elements
    // from the range [2, N]
    $lcm = 1;
    for ($i = 2; $i <= $N; $i++)
        $lcm = (($i * $lcm) / (__gcd($i, $lcm)));
 
    // Return the required number
    return ($lcm + 1);
}
 
function __gcd($a, $b)
{
    if ($b == 0)
        return $a;
    return __gcd($b, $a % $b);
}
 
// Driver code
 
$N = 5;
echo (getMinNum($N));
     
// This code has been contributed by ajit....
?>

<script>
 
// Javascript implementation of the approach
 
// Function to return the smallest number
// which on dividing with any element from
// the range [2, N] leaves a remainder of 1
function getMinNum(N)
{
    // Find the LCM of the elements
    // from the range [2, N]
    var lcm = 1;
    for (var i = 2; i <= N; i++)
        lcm = ((i * lcm) / (__gcd(i, lcm)));
 
    // Return the required number
    return (lcm + 1);
}
 
function __gcd(a, b)
{
    if (b == 0)
        return a;
    return __gcd(b, a % b);
}
 
// Driver code
var N = 5;
document.write( getMinNum(N));
 
</script>

61

Complejidad de tiempo: O(N * log(N) )

Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.