Imprima todos los distintos conjuntos Coprime posibles de 1 a N

Dado un número entero N , la tarea es encontrar todos los conjuntos coprimos distintos hasta el número entero N tal que un elemento no aparezca en más de un conjunto. 

Se dice que un número a es coprimo con b si MCD(a, b) = 1 .

Ejemplos:  

Entrada: N = 5 
Salida: (1, 2) (3, 4, 5) 

Entrada: N = 6 
Salida: (1, 2) (3, 4) (5, 6)  

Acercarse:  

  • Para resolver el problema mencionado anteriormente, podemos observar que si N es menor que 4 entonces todos los elementos ya son coprimos hasta N porque siempre tendrán MCD igual a 1. Así, para N = [1, 3], el posible Los conjuntos coprimos son (1), (1, 2) y (1, 2, 3) respectivamente.
  • Para todos los valores de N > 3, hay dos casos posibles: 
    • Si el valor de N es par , entonces cada conjunto contendrá 2 elementos adyacentes hasta el propio N , ya que los números adyacentes siempre son coprimos entre sí.
    • Si el valor del entero N es impar , entonces cada conjunto contendrá 2 elementos adyacentes excepto el último conjunto que tendrá los últimos tres elementos.

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

C++

// C++ implementation to print
// all distinct co-prime sets
// possible for numbers from 1 to N
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print all coprime sets
void coPrimeSet(int n)
{
 
    int firstadj, secadj;
 
    // Check if n is less than 4
    // then simply print all values till n
    if (n < 4) {
        cout << "( ";
        for (int i = 1; i <= n; i++)
            cout << i << ", ";
 
        cout << ")\n";
    }
 
    // For all the values of n > 3
    else {
 
        // Check if n is even
        // then every set will contain
        // 2 adjacent elements up-to n
        if (n % 2 == 0) {
            for (int i = 0; i < n / 2; i++) {
                firstadj = 2 * i + 1;
                secadj = 2 * i + 2;
 
                cout << "(" << firstadj
                     << ", " << secadj << ")\n";
            }
        }
        else {
 
            // if n is odd then every set will
            // contain 2 adjacent element
            // except the last set which
            // will have last three elements
            for (int i = 0; i < n / 2 - 1; i++)
 
            {
                firstadj = 2 * i + 1;
                secadj = 2 * i + 2;
 
                cout << "(" << firstadj
                     << ", " << secadj << ")\n";
            }
 
            // Last element for odd case
            cout << "(" << n - 2 << ", " << n - 1
                 << ", " << n << ")\n";
        }
    }
}
 
// Driver Code
int main()
{
    int n = 5;
 
    coPrimeSet(n);
 
    return 0;
}

Java

// Java implementation to print
// all distinct co-prime sets
// possible for numbers from 1 to N
import java.util.*;
 
class GFG{
 
// Function to print all co-prime sets
static void coPrimeSet(int n)
{
    int firstadj, secadj;
 
    // Check if n is less than 4 then
    // simply print all values till n
    if (n < 4)
    {
        System.out.print("( ");
        for(int i = 1; i <= n; i++)
           System.out.print(i + ", ");
 
        System.out.print(")\n");
    }
 
    // For all the values of n > 3
    else
    {
         
        // Check if n is even then
        // every set will contain
        // 2 adjacent elements up-to n
        if (n % 2 == 0)
        {
            for(int i = 0; i < n / 2; i++)
            {
               firstadj = 2 * i + 1;
                 secadj = 2 * i + 2;
                
               System.out.print("(" + firstadj +
                               ", " + secadj + ")\n");
            }
        }
        else
        {
 
            // If n is odd then every set will
            // contain 2 adjacent element
            // except the last set which
            // will have last three elements
            for(int i = 0; i < n / 2 - 1; i++)
            {
               firstadj = 2 * i + 1;
                 secadj = 2 * i + 2;
                
               System.out.print("(" + firstadj +
                               ", " + secadj + ")\n");
            }
             
            // Last element for odd case
            System.out.print("(" + (n - 2) +
                            ", " +  ( n - 1) +
                            ", " + n + ")\n");
        }
    }
}
 
// Driver code
public static void main(String[] args)
{
    int n = 5;
 
    coPrimeSet(n);
}
}
 
// This code is contributed by sapnasingh4991

Python3

# Python3 implementation to print
# all distinct co-prime sets
# possible for numbers from 1 to N
 
# Function to print all co-prime sets
def coPrimeSet(n):
     
    firstadj = 0;
    secadj = 0;
 
    # Check if n is less than 4 then
    # simply print all values till n
    if (n < 4):
        print("( ");
         
        for i in range(1, n + 1):
            print(i + ", ");
        print(")");
 
    # For all the values of n > 3
    else:
 
        # Check if n is even then
        # every set will contain
        # 2 adjacent elements up-to n
        if (n % 2 == 0):
             
            for i in range(0, n /2 ):
                firstadj = 2 * i + 1;
                secadj = 2 * i + 2;
                   
                print("(", firstadj, ", ",
                           secadj, ")");
        else:
 
            # If n is odd then every set will
            # contain 2 adjacent element
            # except the last set which
            # will have last three elements
            for i in range(0, int(n / 2) - 1):
                firstadj = 2 * i + 1;
                secadj = 2 * i + 2;
                   
                print("(", firstadj, ", ",
                           secadj, ")");
 
            # Last element for odd case
            print("(", (n - 2), ", ",
                       (n - 1), ", ", n, ")");
                        
# Driver code
if __name__ == '__main__':
     
    n = 5;
 
    coPrimeSet(n);
     
# This code is contributed by 29AjayKumar

C#

// C# implementation to print
// all distinct co-prime sets
// possible for numbers from 1 to N
using System;
 
class GFG{
 
// Function to print all co-prime sets
static void coPrimeSet(int n)
{
    int firstadj, secadj;
 
    // Check if n is less than 4 then
    // simply print all values till n
    if (n < 4)
    {
        Console.Write("( ");
        for(int i = 1; i <= n; i++)
           Console.Write(i + ", ");
 
        Console.Write(")\n");
    }
 
    // For all the values of n > 3
    else
    {
         
        // Check if n is even then
        // every set will contain
        // 2 adjacent elements up-to n
        if (n % 2 == 0)
        {
            for(int i = 0; i < n / 2; i++)
            {
               firstadj = 2 * i + 1;
                 secadj = 2 * i + 2;
                
               Console.Write("(" + firstadj +
                            ", " + secadj + ")\n");
            }
        }
        else
        {
 
            // If n is odd then every set will
            // contain 2 adjacent element
            // except the last set which
            // will have last three elements
            for(int i = 0; i < n / 2 - 1; i++)
            {
               firstadj = 2 * i + 1;
                 secadj = 2 * i + 2;
                 
               Console.Write("(" + firstadj +
                            ", " + secadj + ")\n");
            }
             
            // Last element for odd case
            Console.Write("(" + (n - 2) +
                         ", " + (n - 1) +
                           ", " + n + ")\n");
        }
    }
}
 
// Driver code
public static void Main()
{
    int n = 5;
 
    coPrimeSet(n);
}
}
 
// This code is contributed by Code_Mech

Javascript

<script>
 
// Javascript implementation to print
// all distinct co-prime sets
// possible for numbers from 1 to N
 
// Function to print all co-prime sets
function coPrimeSet(n)
{
    let firstadj, secadj;
   
    // Check if n is less than 4 then
    // simply print all values till n
    if (n < 4)
    {
         document.write("( ");
        for(let i = 1; i <= n; i++)
           document.write(i + ", ");
   
       document.write(")" + "<br/>");
    }
   
    // For all the values of n > 3
    else
    {
           
        // Check if n is even then
        // every set will contain
        // 2 adjacent elements up-to n
        if (n % 2 == 0)
        {
            for(let i = 0; i < Math.floor(n / 2); i++)
            {
               firstadj = 2 * i + 1;
                 secadj = 2 * i + 2;
                  
               document.write("(" + firstadj +
                         ", " + secadj + ")"+ "<br/>");
            }
        }
        else
        {
   
            // If n is odd then every set will
            // contain 2 adjacent element
            // except the last set which
            // will have last three elements
            for(let i = 0; i < Math.floor(n / 2) - 1; i++)
            {
               firstadj = 2 * i + 1;
                 secadj = 2 * i + 2;
                  
               document.write("(" + firstadj +
                               ", " + secadj + ")" + "<br/>");
            }
               
            // Last element for odd case
            document.write("(" + (n - 2) +
                            ", " +  ( n - 1) +
                            ", " + n + ")" + "<br/>");
        }
    }
}
  
  // Driver Code
     
    let n = 5;
   
    coPrimeSet(n);
   
</script>
Producción: 

(1, 2)
(3, 4, 5)

 

Publicación traducida automáticamente

Artículo escrito por KrishnaHare 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 *