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)