Dado un número N , la tarea es imprimir todos los divisores distintos de N 2 .
Ejemplos:
Entrada: N = 4
Salida: 1 2 4 8 16
Explicación:
N = 4, N 2 = 16
Los divisores de 16 son: 1 2 4 8 16Entrada: N = 8
Salida: 1 2 4 8 16 32 64
Enfoque ingenuo:
Encuentre todos los divisores de un número natural usando el enfoque sqrt(N). Pero esta solución no es eficiente ya que la complejidad del tiempo sería O(N) .
Enfoque eficiente:
- Tratamos de generar divisores de N 2 a partir de divisores de N usando el enfoque sqrt(N). Como
Por ejemplo: si N = 4, para generar divisores de 4 2 = 16, primero calcularíamos los divisores de 4 = 1, 2, 4. Ahora iteraremos sobre estos divisores generados para calcular divisores de 4 2 que son 1, 2, 4, 8 y 16.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to print all
// divisors of N*N using N
#include <bits/stdc++.h>
using namespace std;
// Function to find Divisor of N
void DivisorOfN(vector<int>& v,
map<int, bool>& marked,
int n)
{
// sqrt(N) approach
// to find divisors of N
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
if (n / i == i) {
v.push_back(i);
marked[i] = true;
}
else {
v.push_back(i);
v.push_back(n / i);
marked[i] = true;
marked[n / i] = true;
}
}
}
}
// Function to print all divisor of N*N
void PrintDivisors(int n)
{
// Vector v to store divisors of n
vector<int> v;
// Map to avoid repeated divisors
map<int, bool> marked;
// Store all divisor of n
DivisorOfN(v, marked, n);
int size = v.size();
// Iterating over vector v
// to generate divisors of N*N
for (int i = 0; i < size; i++) {
for (int j = i; j < size; j++) {
int check = v[i] * v[j];
// Checking if element is
// already present
if (marked[check] != true) {
v.push_back(v[i] * v[j]);
// marking element true
// after adding in vector
marked[v[i] * v[j]] = true;
}
}
}
sort(v.begin(), v.end());
printf("Divisors of %d are: ", n * n);
for (int i = 0; i < v.size(); i++) {
printf("%d ", v[i]);
}
printf("\n");
}
// Driver Code
int main()
{
PrintDivisors(4);
PrintDivisors(8);
PrintDivisors(10);
return 0;
}
Java
// Java code to print all
// divisors of N*N using N
import java.util.*;
class GFG
{
// Vector v to store divisors of n
static List<Integer> v = new ArrayList<>();
// Map to avoid repeated divisors
static HashMap<Integer, Boolean> marked = new HashMap<>();
// Function to find Divisor of N
static void DivisorOfN(int n)
{
// sqrt(N) approach
// to find divisors of N
for (int i = 1; i <= Math.sqrt(n); i++)
{
if (n % i == 0)
{
if (n / i == i)
{
v.add(i);
marked.put(i, true);
}
else
{
v.add(i);
v.add(n / i);
marked.put(i, true);
marked.put(n / i, true);
}
}
}
}
// Function to print all divisor of N*N
static void PrintDivisors(int n)
{
// Store all divisor of n
DivisorOfN(n);
int size = v.size();
// Iterating over vector v
// to generate divisors of N*N
for (int i = 0; i < size; i++)
{
for (int j = i; j < size; j++)
{
int check = v.get(i) * v.get(j);
// Checking if element is
// already present
if (!marked.containsKey(check))
{
v.add(v.get(i) * v.get(j));
// marking element true
// after adding in vector
marked.put(v.get(i) * v.get(j), true);
}
}
}
Collections.sort(v);
System.out.print("Divisors of " + n * n + " are: ");
for (int i = 0; i < v.size(); i++)
{
System.out.print(v.get(i) + " ");
}
System.out.println();
v.clear();
marked.clear();
}
// Driver code
public static void main(String[] args)
{
PrintDivisors(4);
PrintDivisors(8);
PrintDivisors(10);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 code to print all
# divisors of N*N using
from math import sqrt
# Function to find Divisor of N
def DivisorOfN(v, marked, n):
# sqrt(N) approach
# to find divisors of N
for i in range(1,int(sqrt(n)) + 1, 1):
if (n % i == 0):
if (n // i == i):
v.append(i)
marked[i] = True
else:
v.append(i)
v.append(n // i)
marked[i] = True
marked[n // i] = True
# Function to print all divisor of N*N
def PrintDivisors(n):
# Vector v to store divisors of n
v = []
# Map to avoid repeated divisors
marked = {i:False for i in range(1000)}
# Store all divisor of n
DivisorOfN(v, marked, n)
size = len(v)
# Iterating over vector v
# to generate divisors of N*N
for i in range(size):
for j in range(i,size,1):
check = v[i] * v[j]
# Checking if element is
# already present
if (marked[check] != True):
v.append(v[i] * v[j])
# marking element true
# after adding in vector
marked[v[i] * v[j]] = True
v.sort(reverse = False)
print("Divisors of",n * n,"are: ",end = "")
for i in range(len(v)):
print(v[i],end = " ")
print("\n",end = "")
# Driver Code
if __name__ == '__main__':
PrintDivisors(4)
PrintDivisors(8)
PrintDivisors(10)
# This code is contributed by Bhupendra_Singh
C#
// C# code to print all
// divisors of N*N using N
using System;
using System.Collections.Generic;
class GFG {
// Vector v to store divisors of n
static List<int> v = new List<int>();
// Map to avoid repeated divisors
static Dictionary<int, bool> marked = new Dictionary<int, bool>();
// Function to find Divisor of N
static void DivisorOfN(int n)
{
// sqrt(N) approach
// to find divisors of N
for (int i = 1; i <= Math.Sqrt(n); i++)
{
if (n % i == 0)
{
if (n / i == i)
{
v.Add(i);
marked[i] = true;
}
else
{
v.Add(i);
v.Add(n / i);
marked[i] = true;
marked[n / i] = true;
}
}
}
}
// Function to print all divisor of N*N
static void PrintDivisors(int n)
{
// Store all divisor of n
DivisorOfN(n);
int size = v.Count;
// Iterating over vector v
// to generate divisors of N*N
for (int i = 0; i < size; i++)
{
for (int j = i; j < size; j++)
{
int check = v[i] * v[j];
// Checking if element is
// already present
if (!marked.ContainsKey(check))
{
v.Add(v[i] * v[j]);
// marking element true
// after adding in vector
marked[v[i] * v[j]] = true;
}
}
}
v.Sort();
Console.Write("Divisors of " + n * n + " are: ");
for (int i = 0; i < v.Count; i++)
{
Console.Write(v[i] + " ");
}
Console.WriteLine();
v.Clear();
marked.Clear();
}
// Driver code
static void Main()
{
PrintDivisors(4);
PrintDivisors(8);
PrintDivisors(10);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript code to print all
// divisors of N*N using N
// Function to find Divisor of N
function DivisorOfN(v, marked, n)
{
// sqrt(N) approach
// to find divisors of N
for (var i = 1; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
if (n / i == i) {
v.push(i);
marked[i] = true;
}
else {
v.push(i);
v.push(n / i);
marked[i] = true;
marked[n / i] = true;
}
}
}
}
// Function to print all divisor of N*N
function PrintDivisors(n)
{
// Vector v to store divisors of n
var v = [];
// Map to avoid repeated divisors
var marked = new Map();
// Store all divisor of n
DivisorOfN(v, marked, n);
var size = v.length;
// Iterating over vector v
// to generate divisors of N*N
for (var i = 0; i < size; i++) {
for (var j = i; j < size; j++) {
var check = v[i] * v[j];
// Checking if element is
// already present
if (marked[check] != true) {
v.push(v[i] * v[j]);
// marking element true
// after adding in vector
marked[v[i] * v[j]] = true;
}
}
}
v.sort((a,b)=>a-b)
document.write("Divisors of "+n*n+" are: ");
for (var i = 0; i < v.length; i++) {
document.write(v[i]+ " ");
}
document.write("<br>");
}
// Driver Code
PrintDivisors(4);
PrintDivisors(8);
PrintDivisors(10);
</script>
Producción:
Divisors of 16 are: 1 2 4 8 16 Divisors of 64 are: 1 2 4 8 16 32 64 Divisors of 100 are: 1 2 4 5 10 20 25 50 100
Complejidad de tiempo: O(sqrt(N) + a 2 ) donde a es un número de divisores de N.
Nota: ¿En qué se diferencia este enfoque de Encontrar todos los divisores de un número natural ?
Sea N = 5, por lo tanto necesitamos encontrar todos los divisores de 25.
- Usando el enfoque usado en Encontrar todos los divisores de un número natural : iteraremos usando i de 1 a sqrt(25) = 5 y verificaremos i y n/i.
Complejidad del tiempo: O(sqrt(25))
- Usando el enfoque usado en este artículo: encontraremos un divisor de 5 usando el enfoque de los artículos mencionados anteriormente que se hará en complejidad de tiempo sqrt(5). Ahora, para todos los divisores de 5, es decir, 1, 5, almacenaremos esto en una array y lo multiplicaremos por pares con la ayuda de 2 bucles {(1*1, 1*5, 5*1, 5*5)} y elegiremos el único unos, es decir, 1, 5, 25. Esto tomará ^ 2 veces (donde a es el número del divisor de 5, que aquí es 2)
Complejidad de tiempo: O (raíz cuadrada (5) + 2 ^ 2)
Este artículo solo funciona mejor que el artículo antes mencionado cuando el número de divisores del número es menor.
Publicación traducida automáticamente
Artículo escrito por saurabhshadow y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA