Dado un entero positivo N , la tarea es imprimir todos los números, digamos K , de modo que K sea un divisor de N y K y N/K sean coprimos .
Ejemplos:
Entrada: N = 12
Salida: 1 3 4 12
Explicación:
Todos los números K tales que es divisor de N(= 12) y K y N/K son coprimos:
- 1: Dado que 1 es un divisor de 12 y 1 y 12 (= 12/1) son coprimos.
- 3: Dado que 3 es un divisor de 12 y 3 y 4 (= 12/3) son coprimos.
- 4: Dado que 4 es un divisor de 12 y 4 y 3 (= 12/4) son coprimos.
- 12: Dado que 12 es un divisor de 12 y 12 y 1 (= 12/12) son coprimos.
Entrada: N = 100
Salida: 1 4 25 100
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es iterar sobre el rango [1, N] y verificar para cada número K si K es un divisor de N y MCD de K y N/K es 1 o no. Si se encuentra que es cierto , imprima K. De lo contrario, busque el siguiente número.
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando la observación de que todos los divisores están presentes en pares. Por ejemplo, si N es 100 , entonces todos los pares de divisores son: (1, 100), (2, 50), (4, 25), (5, 20), (10, 10) .
Por lo tanto, la idea es iterar en el rango [1, √N] y verificar si ambas condiciones dadas se cumplen o no, es decir, si cualquier número K es un divisor de N y MCD de K y N/K es 1 o no . . Si se encuentra que es cierto , imprima ambos números. En el caso de dos divisores iguales, imprima solo uno de ellos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print all numbers // that are divisors of N and are // co-prime with the quotient // of their division void printUnitaryDivisors(int n) { // Iterate upto square root of N for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { // If divisors are equal and gcd is // 1, then print only one of them if (n / i == i && __gcd(i, n / i) == 1) { printf("%d ", i); } // Otherwise print both else { if (__gcd(i, n / i) == 1) { printf("%d %d ", i, n / i); } } } } } // Driver Code int main() { int N = 12; printUnitaryDivisors(N); return 0; }
Python3
# python 3 program for the above approach from math import sqrt, gcd # Function to print all numbers # that are divisors of N and are # co-prime with the quotient # of their division def printUnitaryDivisors(n): # Iterate upto square root of N for i in range(1,int(sqrt(n)) + 1, 1): if (n % i == 0): # If divisors are equal and gcd is # 1, then print only one of them if (n // i == i and gcd(i, n // i) == 1): print(i) # Otherwise print both else: if (gcd(i, n // i) == 1): print(i, n // i,end = " ") # Driver Code if __name__ == '__main__': N = 12 printUnitaryDivisors(N) # This code is contributed by ipg2016107.
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } // Function to print all numbers // that are divisors of N and are // co-prime with the quotient // of their division static void printUnitaryDivisors(int n) { // Iterate upto square root of N for (int i = 1; i <= (int)Math.Sqrt(n); i++) { if (n % i == 0) { // If divisors are equal and gcd is // 1, then print only one of them if (n / i == i && gcd(i, n / i) == 1) { Console.Write(i+" "); } // Otherwise print both else { if (gcd(i, n / i) == 1) { Console.Write(i + " " +n / i+ " "); } } } } } // Driver Code public static void Main() { int N = 12; printUnitaryDivisors(N); } } // This code is contributed by SURENDRA_GANGWAR.
Java
// Java program for the above approach import java.util.*; class GFG { static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } // Function to print all numbers // that are divisors of N and are // co-prime with the quotient // of their division static void printUnitaryDivisors(int n) { // Iterate upto square root of N for (int i = 1; i <= (int)Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal and gcd is // 1, then print only one of them if (n / i == i && gcd(i, n / i) == 1) { System.out.print(i + " "); } // Otherwise print both else { if (gcd(i, n / i) == 1) { System.out.print(i + " " + n / i + " "); } } } } } // Driver Code public static void main(String[] args) { int N = 12; printUnitaryDivisors(N); } }
Javascript
<script> // JavaScript program for the above approach function gcd( a, b) { return b == 0 ? a : gcd(b, a % b); } // Function to print all numbers // that are divisors of N and are // co-prime with the quotient // of their division function printUnitaryDivisors( n) { // Iterate upto square root of N for (var i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal and gcd is // 1, then print only one of them if (n / i == i && gcd(i, n / i) == 1) { document.write(i + " "); } // Otherwise print both else { if (gcd(i, n / i) == 1) { document.write(i + " " + n / i + " "); } } } } } // Driver Code var N = 12; printUnitaryDivisors(N); // This code is contributed by shivanisingh2110 </script>
1 12 3 4
Complejidad de tiempo: O(√N*log N)
Espacio auxiliar: O(1)