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