Dado un número natural n, imprima todos los divisores distintos de él.
Ejemplos:
Input : n = 10 Output: 1 2 5 10 Input: n = 100 Output: 1 2 4 5 10 20 25 50 100 Input: n = 125 Output: 1 5 25 125
Tenga en cuenta que este problema es diferente de encontrar todos los factores primos .
Una solución ingenua sería iterar todos los números del 1 al n, verificar si ese número divide n e imprimirlo. A continuación se muestra un programa para el mismo:
C++
// C++ implementation of Naive method to print all
// divisors
#include <iostream>
using namespace std;
// function to print the divisors
void printDivisors(int n)
{
for (int i = 1; i <= n; i++)
if (n % i == 0)
cout <<" " << i;
}
/* Driver program to test above function */
int main()
{
cout <<"The divisors of 100 are: \n";
printDivisors(100);
return 0;
}
// this code is contributed by shivanisinghss2110
C
// C implementation of Naive method to print all
// divisors
#include<stdio.h>
// function to print the divisors
void printDivisors(int n)
{
for (int i=1;i<=n;i++)
if (n%i==0)
printf("%d ",i);
}
/* Driver program to test above function */
int main()
{
printf("The divisors of 100 are: \n");
printDivisors(100);
return 0;
}
Java
// Java implementation of Naive method to print all
// divisors
class Test
{
// method to print the divisors
static void printDivisors(int n)
{
for (int i=1;i<=n;i++)
if (n%i==0)
System.out.print(i+" ");
}
// Driver method
public static void main(String args[])
{
System.out.println("The divisors of 100 are: ");
printDivisors(100);;
}
}
Python3
# Python implementation of Naive method
# to print all divisors
# method to print the divisors
def printDivisors(n) :
i = 1
while i <= n :
if (n % i==0) :
print (i,end=" ")
i = i + 1
# Driver method
print ("The divisors of 100 are: ")
printDivisors(100)
#This code is contributed by Nikita Tiwari.
C#
// C# implementation of Naive method
// to print all divisors
using System;
class GFG {
// method to print the divisors
static void printDivisors(int n)
{
for (int i = 1; i <= n; i++)
if (n % i == 0)
Console.Write( i + " ");
}
// Driver method
public static void Main()
{
Console.Write("The divisors of",
" 100 are: ");
printDivisors(100);;
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP implementation of Naive
// method to print all divisors
// function to print the divisors
function printDivisors($n)
{
for ($i = 1; $i <= $n; $i++)
if ($n % $i == 0)
echo $i," ";
}
// Driver Code
echo "The divisors of 100 are:\n";
printDivisors(100);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript implementation of Naive method to print all
// divisors
// function to print the divisors
function printDivisors(n)
{
for (i=1;i<=n;i++)
if (n%i==0)
document.write(i+ " ");
}
/* Driver program to test above function */
document.write("The divisors of 100 are:" + "<br>");
printDivisors(100);
// This code is contributed by Mayank Tyagi
</script>
Producción:
The divisors of 100 are: 1 2 4 5 10 20 25 50 100
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)
¿Podemos mejorar la solución anterior?
Si nos fijamos bien, todos los divisores están presentes en pares. Por ejemplo, si n = 100, entonces los varios pares de divisores son: (1,100), (2,50), (4,25), (5,20), (10,10)
Usando este hecho podríamos acelerar nuestra programa significativamente.
Sin embargo, debemos tener cuidado si hay dos divisores iguales como en el caso de (10, 10). En tal caso, imprimiríamos solo uno de ellos.
A continuación se muestra una implementación para el mismo:
C++
// A Better (than Naive) Solution to find all divisors
#include <iostream>
#include <math.h>
using namespace std;
// Function to print the divisors
void printDivisors(int n)
{
// Note that this loop runs till square root
for (int i=1; i<=sqrt(n); i++)
{
if (n%i == 0)
{
// If divisors are equal, print only one
if (n/i == i)
cout <<" "<< i;
else // Otherwise print both
cout << " "<< i << " " << n/i;
}
}
}
/* Driver program to test above function */
int main()
{
cout <<"The divisors of 100 are: \n";
printDivisors(100);
return 0;
}
// this code is contributed by shivanisinghss2110
C
// A Better (than Naive) Solution to find all divisors
#include <stdio.h>
#include <math.h>
// Function to print the divisors
void printDivisors(int n)
{
// Note that this loop runs till square root
for (int i=1; i<=sqrt(n); i++)
{
if (n%i == 0)
{
// If divisors are equal, print only one
if (n/i == i)
printf("%d ", i);
else // Otherwise print both
printf("%d %d ", i, n/i);
}
}
}
/* Driver program to test above function */
int main()
{
printf("The divisors of 100 are: \n");
printDivisors(100);
return 0;
}
Java
// A Better (than Naive) Solution to find all divisors
class Test
{
// method to print the divisors
static void printDivisors(int n)
{
// Note that this loop runs till square root
for (int i=1; i<=Math.sqrt(n); i++)
{
if (n%i==0)
{
// If divisors are equal, print only one
if (n/i == i)
System.out.print(" "+ i);
else // Otherwise print both
System.out.print(i+" " + n/i + " " );
}
}
}
// Driver method
public static void main(String args[])
{
System.out.println("The divisors of 100 are: ");
printDivisors(100);;
}
}
Python3
# A Better (than Naive) Solution to find all divisors
import math
# method to print the divisors
def printDivisors(n) :
# Note that this loop runs till square root
i = 1
while i <= math.sqrt(n):
if (n % i == 0) :
# If divisors are equal, print only one
if (n / i == i) :
print (i,end=" ")
else :
# Otherwise print both
print (i , int(n/i), end=" ")
i = i + 1
# Driver method
print ("The divisors of 100 are: ")
printDivisors(100)
#This code is contributed by Nikita Tiwari.
C#
// A Better (than Naive) Solution to
// find all divisors
using System;
class GFG {
// method to print the divisors
static void printDivisors(int n)
{
// Note that this loop runs
// till square root
for (int i = 1; i <= Math.Sqrt(n);
i++)
{
if (n % i == 0)
{
// If divisors are equal,
// print only one
if (n / i == i)
Console.Write(i + " ");
// Otherwise print both
else
Console.Write(i + " "
+ n / i + " ");
}
}
}
// Driver method
public static void Main()
{
Console.Write("The divisors of "
+ "100 are: \n");
printDivisors(100);
}
}
// This code is contributed by Smitha
PHP
<?php
// A Better (than Naive) Solution
// to find all divisors
// Function to print the divisors
function printDivisors($n)
{
// Note that this loop
// runs till square root
for ($i = 1; $i <= sqrt($n); $i++)
{
if ($n%$i == 0)
{
// If divisors are equal,
// print only one
if ($n / $i == $i)
echo $i," ";
// Otherwise print both
else
echo $i," ", $n/$i," ";
}
}
}
// Driver Code
echo "The divisors of 100 are: \n";
printDivisors(100);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// A Better (than Naive) Solution to find all divisors
// Function to print the divisors
function printDivisors(n)
{
// Note that this loop runs till square root
for(let i = 1; i <= Math.sqrt(n); i++)
{
if (n % i == 0)
{
// If divisors are equal, print only one
if (parseInt(n / i, 10) == i)
document.write(i);
// Otherwise print both
else
document.write(i + " " +
parseInt(n / i, 10) + " ");
}
}
}
// Driver code
document.write("The divisors of 100 are: </br>");
printDivisors(100);
// This code is contributed by divyesh072019
</script>
Producción:
The divisors of 100 are: 1 100 2 50 4 25 5 20 10
Complejidad de tiempo: O(sqrt(n))
Espacio auxiliar: O(1)
Sin embargo, todavía hay un problema menor en la solución, ¿puedes adivinar?
¡Sí! la salida no está ordenada como la que obtuvimos usando la técnica de fuerza bruta. Consulte a continuación una solución de tiempo O(sqrt(n)) que imprime los divisores en orden ordenado.
Encuentra todos los divisores de un número natural | Conjunto 2
Este artículo es una contribución de Ashutosh Kumar . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA