Encuentra todos los divisores de un número natural | conjunto 2

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 

Recomendamos encarecidamente consultar el siguiente artículo como requisito previo. 
Encuentra todos los divisores de un número natural | Conjunto 1
En la publicación anterior, habíamos encontrado una forma de encontrar todos los divisores en O(sqrt(n)).
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.

¿Cómo imprimir la salida en orden ordenado?  
Si observamos la salida que obtuvimos, podemos analizar que los divisores están impresos en zig-zag (pequeño, par grande). Por lo tanto, si almacenamos la mitad de ellos, podemos imprimirlos en orden. 

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

// A O(sqrt(n)) program that prints all divisors
// in sorted order
#include <bits/stdc++.h>
using namespace std;
 
// function to print the divisors
void printDivisors(int n)
{
    // Vector to store half of the divisors
    vector<int> v;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
 
            // check if divisors are equal
            if (n / i == i)
                printf("%d ", i);
            else {
                printf("%d ", i);
 
                // push the second divisor in the vector
                v.push_back(n / i);
            }
        }
    }
 
    // The vector will be printed in reverse
    for (int i = v.size() - 1; i >= 0; i--)
        printf("%d ", v[i]);
}
 
/* Driver program to test above function */
int main()
{
    printf("The divisors of 100 are: \n");
    printDivisors(100);
    return 0;
}

// A O(sqrt(n)) java program that prints all divisors
// in sorted order
 
import java.util.Vector;
 
class Test {
    // method to print the divisors
    static void printDivisors(int n)
    {
        // Vector to store half of the divisors
        Vector<Integer> v = new Vector<>();
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
 
                // check if divisors are equal
                if (n / i == i)
                    System.out.printf("%d ", i);
                else {
                    System.out.printf("%d ", i);
 
                    // push the second divisor in the vector
                    v.add(n / i);
                }
            }
        }
 
        // The vector will be printed in reverse
        for (int i = v.size() - 1; i >= 0; i--)
            System.out.printf("%d ", v.get(i));
    }
 
    // Driver method
    public static void main(String args[])
    {
        System.out.println("The divisors of 100 are: ");
        printDivisors(100);
    }
}

# A O(sqrt(n)) java program that prints
# all divisors in sorted order
import math
 
# Method to print the divisors
def printDivisors(n) :
    list = []
     
    # List to store half of the divisors
    for i in range(1, int(math.sqrt(n) + 1)) :
         
        if (n % i == 0) :
             
            # Check if divisors are equal
            if (n / i == i) :
                print (i, end =" ")
            else :
                # Otherwise print both
                print (i, end =" ")
                list.append(int(n / i))
                 
    # The list will be printed in reverse   
    for i in list[::-1] :
        print (i, end =" ")
         
# Driver method
print ("The divisors of 100 are: ")
printDivisors(100)
 
# This code is contributed by Gitanjali

// A O(sqrt(n)) C# program that
// prints all divisors in sorted order
using System;
 
class GFG {
 
    // method to print the divisors
    static void printDivisors(int n)
    {
        // Vector to store half
        // of the divisors
        int[] v = new int[n];
        int t = 0;
        for (int i = 1;
             i <= Math.Sqrt(n); i++) {
            if (n % i == 0) {
 
                // check if divisors are equal
                if (n / i == i)
                    Console.Write(i + " ");
                else {
                    Console.Write(i + " ");
 
                    // push the second divisor
                    // in the vector
                    v[t++] = n / i;
                }
            }
        }
 
        // The vector will be
        // printed in reverse
        for (int i = t - 1; i >= 0; i--)
            Console.Write(v[i] + " ");
    }
 
    // Driver Code
    public static void Main()
    {
        Console.Write("The divisors of 100 are: \n");
        printDivisors(100);
    }
}
 
// This code is contributed
// by ChitraNayal

<?php
// A O(sqrt(n)) program that
// prints all divisors in
// sorted order
 
// function to print
// the divisors
function printDivisors($n)
{
    // Vector to store half
    // of the divisors
    $v;
    $t = 0;
    for ($i = 1;
         $i <= (int)sqrt($n); $i++)
    {
        if ($n % $i == 0)
        {
            // check if divisors are equal
            if ((int)$n / $i == $i)
                echo $i . " ";
            else
            {
                echo $i . " ";
 
                // push the second
                // divisor in the vector
                $v[$t++] = (int)$n / $i;
            }
        }
    }
 
    // The vector will be
    // printed in reverse
    for ($i = count($v) - 1;
         $i >= 0; $i--)
        echo $v[$i] . " ";
}
 
// Driver code
echo "The divisors of 100 are: \n";
printDivisors(100);
 
// This code is contributed by mits
?>

<script>
 
// A O(sqrt(n)) program that
// prints all divisors in
// sorted order
 
// function to print
// the divisors
function printDivisors(n)
{
    // Vector to store half
    // of the divisors
    let v = [];
    let t = 0;
    for (let i = 1;
         i <= parseInt(Math.sqrt(n)); i++)
    {
        if (n % i == 0)
        {
            // check if divisors are equal
            if (parseInt(n / i) == i)
                document.write(i + " ");
            else
            {
                document.write(i + " ");
 
                // push the second
                // divisor in the vector
                v[t++] = parseInt(n / i);
            }
        }
    }
 
    // The vector will be
    // printed in reverse
    for (let i = v.length - 1;
         i >= 0; i--){
         document.write(v[i] + " ");
    }
}
 
// Driver code
document.write("The divisors of 100 are: \n");
printDivisors(100);
 
// This code is contributed by _saurabh_jaiswal
 
</script>

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

Complejidad de tiempo : O(sqrt(n)) 
Espacio auxiliar : O(sqrt(n))

Método 2:

Enfoque: En el siguiente enfoque usando for loop, primero estamos imprimiendo los únicos números que dejan un resto 0 y una vez que rompemos el ciclo, solo estamos imprimiendo el cociente de los números que dan un resto como 0.

vamos a entender a través del ejemplo: 

n = 10 
from 1 to 10
keep checking n % 1 == 0 print 1
              n % 2 == 0 print 2
              3, 4, 5, 6, 7, 8, 9 will not give remainder 0 
              exit loop;
              
The 1 and 2 which gives remainder as 0 it also mean that n is perfectly divisible by 1 and 2 so in second for loop keep printing the quotient on dividing by 1 and 2 which left remainder 0
from 10 to 1 
keep checking n % 1 == 0 print n/1 
              n % 2 == 0 print n/2   
              exit loop

// A O(sqrt(n)) program that prints all divisors
// in sorted order
#include <iostream>
#include <math.h>
using namespace std;
 
// Function to print the divisors
void printDivisors(int n)
{
    int i;
    for (i = 1; i * i < n; i++) {
        if (n % i == 0)
            cout<<i<<" ";
    }
    if (i - (n / i) == 1) {
        i--;
    }
    for (; i >= 1; i--) {
        if (n % i == 0)
            cout<<n / i<<" ";
    }
}
 
// Driver code
int main()
{
    cout << "The divisors of 100 are: \n";
 
    printDivisors(100);
 
    return 0;
}
 
// This code is contributed by siteshbiswal

// A O(sqrt(n)) program that prints all divisors
// in sorted order
#include <stdio.h>
#include <math.h>
 
// function to print the divisors
void printDivisors(int n)
{ int i;
    for ( i = 1; i*i < n; i++) {
        if (n % i == 0)
            printf("%d ", i);
    }
   if(i-(n/i)==1)
    {
      i--;
    }
    for (; i >= 1; i--) {
        if (n % i == 0)
            printf("%d ", n / i);
    }
}
 
/* Driver program to test above function */
int main()
{
    printf("The divisors of 100 are: \n");
    printDivisors(100);
    return 0;
}

// A O(sqrt(n)) program that prints all
// divisors in sorted order
import java.lang.Math;
 
class GFG{
     
// Function to print the divisors
public static void printDivisors(int n)
{ int i;
    for( i = 1; i * i < n; i++)
    {
        if (n % i == 0)
            System.out.print(i + " ");
    }
    if(i-(n/i)==1)
    {
      i--;
    }
    for(; i >= 1; i--)
    {
        if (n % i == 0)
            System.out.print(n / i + " ");
    }
}
 
// Driver code
public static void main(String[] args)
{
    System.out.println("The divisors of 100 are: ");
     
    printDivisors(100);
}
}
 
// This code is contributed by Prakash Veer Singh Tomar.

# A O(sqrt(n)) program that prints all divisors
# in sorted order
from math import *
 
# Function to print the divisors
def printDivisors (n):
 
    i = 1
    while (i * i < n):
        if (n % i == 0):
            print(i, end = " ")
 
        i += 1
 
    for i in range(int(sqrt(n)), 0, -1):
        if (n % i == 0):
            print(n // i, end = " ")
 
# Driver Code
print("The divisors of 100 are: ")
 
printDivisors(100)
 
# This code is contributed by himanshu77

// A O(sqrt(n)) program that prints
// all divisors in sorted order
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG{
 
// Function to print the divisors
static void printDivisors(int n)
{
    for(int i = 1; i * i < n; i++)
    {
        if (n % i == 0)
            Console.Write(i + " ");
    }
    for(int i = (int)Math.Sqrt(n); i >= 1; i--)
    {
        if (n % i == 0)
            Console.Write(n / i + " ");
    }
} 
  
// Driver code  
public static void Main(string []arg)
{
    Console.Write("The divisors of 100 are: \n");
     
    printDivisors(100);
}
}
 
// This code is contributed by rutvik_56

<script>
 
// A O(sqrt(n)) program that prints all divisors
// in sorted order
 
// function to print the divisors
function printDivisors(n)
{
    for (var i = 1; i*i < n; i++) {
        if (n % i == 0)
            document.write(i + " ");
    }
    for (var i = Math.sqrt(n); i >= 1; i--) {
        if (n % i == 0)
            document.write(" " + n / i);
    }
}
 
// Driver program to test above function
 
    document.write("The divisors of 100 are: \n");
    printDivisors(100);
     
// This code is contributed by simranarora5sos
 
</script>

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

Complejidad del tiempo: O(sqrt(n)) 

Espacio auxiliar: O(1) 
Gracias a Mysterious Mind por sugerir la solución anterior.

La condición if entre los dos bucles se usa cuando los factores de esquina en la condición de los bucles tienen una diferencia de 1 (ejemplo: factores de 30 (5,6) aquí, 5 se imprimirá dos veces; para resolver ese problema, se requiere este paso).

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.