Encuentra todos los factores del número natural

Dado un número natural n, imprima cada división distinta del mismo.

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.

A solución ingenua todos los números desde el 1 hasta las repeticiones, comprobando si ese número divide a n e imprimiéndolo. A continuación se muestra un programa para el mismo:

Tabla de contenidos

C++

#include <iostream>

using namespace std;

void printDivisors(int n)

{

for (int i = 1; i <= n; i++)

if (n % i == 0)

cout <<" " << i;

}

int main()

{

cout <<"The divisors of 100 are: n";

printDivisors(100);

return 0;

}

C

#include<stdio.h>

void printDivisors(int n)

{

for (int i=1;i<=n;i++)

if (n%i==0)

printf("%d ",i);

}

int main()

{

printf("The divisors of 100 are: n");

printDivisors(100);

return 0;

}

Java

class Test

{

static void printDivisors(int n)

{

for (int i=1;i<=n;i++)

if (n%i==0)

System.out.print(i+" ");

}

public static void main(String args[])

{

System.out.println("The divisors of 100 are: ");

printDivisors(100);;

}

Python3

def printDivisors(n) :

i = 1

while i <= n :

if (n % i==0) :

print (i,end=" ")

i = i + 1

print ("The divisors of 100 are: ")

printDivisors(100)

C#

using System;

class GFG {

static void printDivisors(int n)

{

for (int i = 1; i <= n; i++)

if (n % i == 0)

Console.Write( i + " ");

}

public static void Main()

{

Console.Write("The divisors of",

" 100 are: ");

printDivisors(100);;

}

PHP

<?php

function printDivisors($n)

{

for ($i = 1; $i <= $n; $i++)

if ($n % $i == 0)

echo $i," ";

}

echo "The divisors of 100 are:n";

printDivisors(100);

?>

JavaScript

<script>

function printDivisors(n)

{

for (i=1;i<=n;i++)

if (n%i==0)

document.write(i+ " ");

}

document.write("The divisors of 100 are:" + "<br>");

printDivisors(100);

</script>

Producción:

The divisors of 100 are: 
1 2 4 5 10 20 25 50 100

Complejidad del tiempo: Desde el)
Espacio Auxiliar : O(1)

¿Podemos mejorar la solución anterior?
Si miramos con atención, todos los divisores están presentes en pares. Por ejemplo si n = 100, los diferentes pares de divisores son: (1,100), (2,50), (4,25), (5,20), (10,10)
Usando este hecho podríamos acelerar mucho nuestro programa.
Sin embargo, debemos tener cuidado si hay dos divisores iguales como en el caso de (10, 10). En tal caso, queremos imprimir solo uno de ellos.

A continuación se muestra una implementación para el mismo:

C++

#include <iostream>

#include <math.h>

using namespace std;

void printDivisors(int n)

{

for (int i=1; i<=sqrt(n); i++)

{

if (n%i == 0)

{

if (n/i == i)

cout <<" "<< i;

else

cout << " "<< i << " " << n/i;

}

int main()

{

cout <<"The divisors of 100 are: n";

printDivisors(100);

return 0;

}

C

#include <stdio.h>

#include <math.h>

void printDivisors(int n)

{

for (int i=1; i<=sqrt(n); i++)

{

if (n%i == 0)

{

if (n/i == i)

printf("%d ", i);

else

printf("%d %d ", i, n/i);

}

int main()

{

printf("The divisors of 100 are: n");

printDivisors(100);

return 0;

}

Java

class Test

{

static void printDivisors(int n)

{

for (int i=1; i<=Math.sqrt(n); i++)

{

if (n%i==0)

{

if (n/i == i)

System.out.print(" "+ i);

else

System.out.print(i+" " + n/i + " " );

}

public static void main(String args[])

{

System.out.println("The divisors of 100 are: ");

printDivisors(100);;

}

Python3

import math

def printDivisors(n) :

i = 1

while i <= math.sqrt(n):

if (n % i == 0) :

if (n / i == i) :

print (i,end=" ")

else :

print (i , int(n/i), end=" ")

i = i + 1

print ("The divisors of 100 are: ")

printDivisors(100)

C#

using System;

class GFG {

static void printDivisors(int n)

{

for (int i = 1; i <= Math.Sqrt(n);

i++)

{

if (n % i == 0)

{

if (n / i == i)

Console.Write(i + " ");

else

Console.Write(i + " "

+ n / i + " ");

}

public static void Main()

{

Console.Write("The divisors of "

+ "100 are: n");

printDivisors(100);

}

PHP

<?php

function printDivisors($n)

{

for ($i = 1; $i <= sqrt($n); $i++)

{

if ($n%$i == 0)

{

if ($n / $i == $i)

echo $i," ";

else

echo $i," ", $n/$i," ";

}

echo "The divisors of 100 are: n";

printDivisors(100);

?>

JavaScript

<script>

function printDivisors(n)

{

for(let i = 1; i <= Math.sqrt(n); i++)

{

if (n % i == 0)

{

if (parseInt(n / i, 10) == i)

document.write(i);

else

document.write(i + " " +

parseInt(n / i, 10) + " ");

}

document.write("The divisors of 100 are: </br>");

printDivisors(100);

</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 pequeño problema 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.
Encuentra todos los divisores de un número natural | conjunto 2
Este artículo ha sido agregado Ashutosh Kumar. Escriba un comentario si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Encuentra todos los factores del número natural | Serie 1

C++

C

Java

Python3

C#

PHP

JavaScript

C++

C

Java

Python3

C#

PHP

JavaScript

Deja un comentario Cancelar respuesta

C++

C

Java

Python3

C#

PHP

JavaScript

C++

C

Java

Python3

C#

PHP

JavaScript

Seguro que también te interesa

Deja un comentario Cancelar respuesta