Agrupar todos los números coprimos del 1 al N

Dado un número entero N , la tarea es agrupar números de manera que cada grupo sea coprimo entre sí y la agrupación total sea mínima.

Ejemplos:

Entrada: N = 8 
Salida: 
1 2 3 
4 5 
6 7 
8

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

Enfoque: La observación clave en este problema es que dos números consecutivos siempre son coprimos. Eso es GCD(a, a+1) = 1. Otra observación importante es que los números pares no se pueden enumerar en un grupo. Porque conducirán al máximo común divisor de 2. Por lo tanto, todos los números pares e impares consecutivos se pueden agrupar en un grupo y 1 puede estar en cualquier grupo porque el máximo común divisor de los números con 1 es siempre 1.

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

// C++ implementation to group
// mutually coprime numbers into
// one group with minimum group possible
#include<bits/stdc++.h>
using namespace std;
 
// Function to group the mutually
// co-prime numbers into one group
void mutually_coprime(int n)
{
    if (n <= 3)
    {
         
        // Loop for the numbers less
        // than the 4
        for(int j = 1; j <= n; j++)
        {
            cout << j << " ";
        }
        cout << "\n";
    }
    else
    {
         
        // Integers 1, 2 and 3 can be
        // grouped into one group
        cout << "1 2 3\n";
         
        for(int j = 4; j < n; j += 2)
        {
             
            // Consecutive even and
            // odd numbers
            cout << j << " " << j + 1 << "\n";
        }
        if(n % 2 == 0)
            cout << n << "\n";
    }
}
 
// Driver Code        
int main()
{
    int n = 9;
     
    // Function call
    mutually_coprime(n);
}
 
// This code is contributed by yatinagg

// Java implementation to group
// mutually coprime numbers into
// one group with minimum group possible
class GFG{
     
// Function to group the mutually
// co-prime numbers into one group
static void mutually_coprime(int n)
{
    if (n <= 3)
    {
         
        // Loop for the numbers less
        // than the 4
        for(int j = 1; j < n + 1; j++)
           System.out.print(j + " ");
        System.out.println();
    }
    else
    {
         
        // Integers 1, 2 and 3 can be
        // grouped into one group
        System.out.println("1 2 3");
        for(int j = 4; j < n; j += 2)
        {
 
           // Consecutive even and
           // odd numbers
           System.out.println(j + " " + (j + 1));
           if (n % 2 == 0)
           System.out.println(n);
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 9;
 
    // Function Call
    mutually_coprime(n);
}
}
 
// This code is contributed by sapnasingh4991

# Python3 implementation to group
# mutually coprime numbers into
# one group with minimum group possible
 
# Function to group the mutually
# co-prime numbers into one group
def mutually_coprime (n):   
    if ( n <= 3):
        # Loop for the numbers less
        # than the 4
        for j in range (1, n + 1):
            print (j, end =" ")
        print ()
    else:
        # Integers 1, 2 and 3 can be
        # grouped into one group
        print (1, 2, 3)
        for j in range ( 4, n, 2 ):
             
            # Consecutive even and
            # odd numbers
            print (j, ( j + 1 ))
        if(n % 2 == 0):        
            print (n)
 
# Driver Code           
if __name__ == "__main__":
    n = 9
     
    # Function Call
    mutually_coprime (n)

// C# implementation to group
// mutually coprime numbers into
// one group with minimum group possible
using System;
 
class GFG{
     
// Function to group the mutually
// co-prime numbers into one group
static void mutually_coprime(int n)
{
    if (n <= 3)
    {
         
        // Loop for the numbers less
        // than the 4
        for(int j = 1; j < n + 1; j++)
           Console.Write(j + " ");
            
        Console.WriteLine();
    }
    else
    {
         
        // ints 1, 2 and 3 can be
        // grouped into one group
        Console.WriteLine("1 2 3");
        for(int j = 4; j < n; j += 2)
        {
           // Consecutive even and
           // odd numbers
           Console.WriteLine(j + " " + (j + 1));
             
           if (n % 2 == 0)
               Console.WriteLine(n);
        }
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int n = 9;
 
    // Function Call
    mutually_coprime(n);
}
}
// This code is contributed by sapnasingh4991

<script>
 
// Javascript implementation to group
// mutually coprime numbers into
// one group with minimum group possible
 
// Function to group the mutually
// co-prime numbers into one group
function mutually_coprime(n)
{
    if (n <= 3)
    {
           
        // Loop for the numbers less
        // than the 4
        for(let j = 1; j < n + 1; j++)
           document.write(j + " " + "<br/>");
        document.write("<br/>");
    }
    else
    {
           
        // Integers 1, 2 and 3 can be
        // grouped into one group
        document.write("1 2 3" + "<br/>");
        for(let j = 4; j < n; j += 2)
        {
   
           // Consecutive even and
           // odd numbers
           document.write(j + " " + (j + 1) + "<br/>");
           if (n % 2 == 0)
           document.write(n + "<br/>");
        }
    }
}
   
 
// Driver Code
     
    let n = 9;
   
    // Function Call
    mutually_coprime(n);
       
</script>

1 2 3
4 5
6 7
8 9         

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)