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

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:

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.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Salir de la versión móvil