Найти все делители натурального числа | Комплект 2

Опубликовано: 20 Января, 2022

Для натурального числа n выведите все его различные делители.

Примеры:

 Ввод: n = 10       
 Выход: 1 2 5 10

 Ввод: n = 100.
 Выход: 1 2 4 5 10 20 25 50 100

 Ввод: n = 125.
 Выход: 1 5 25 125

Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

Мы настоятельно рекомендуем ссылаться на приведенную ниже статью в качестве обязательного условия.
Найти все делители натурального числа | Комплект 1
В сообщении выше мы нашли способ найти все делители в O (sqrt (n)).
Однако в решении все еще есть небольшая проблема, вы можете догадаться?
Да! вывод не находится в отсортированном виде, который мы получили с помощью метода грубой силы.

Как распечатать результат в отсортированном порядке?
Если мы наблюдаем результат, который мы получили, мы можем проанализировать, что делители напечатаны зигзагообразно (маленькие, большие пары). Следовательно, если мы сохраним половину из них, мы сможем распечатать их в отсортированном порядке.

Ниже приведена реализация того же:

Выход :

 Делители 100: 
1 2 4 5 10 20 25 50 100

Сложность времени: O (sqrt (n))
Вспомогательное пространство: O (sqrt (n))

A O(sqrt(n)) Time and O(1) Space Solution :

C++

// 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)
{
    for (int i = 1; i*i < n; i++) {
        if (n % i == 0)
            printf("%d ", i);
    }
    for (int i = sqrt(n); 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: 
");
    printDivisors(100);
    return 0;
}

Java

// 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)
{
    for(int i = 1; i * i < n; i++)
    {
        if (n % i == 0)
            System.out.print(i + " ");
    }
    for(int i = (int)Math.sqrt(n);
            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 divyeshrabadiya07

Python3

# 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

C#

// 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: 
");
     
    printDivisors(100);
}
}
 
// This code is contributed by rutvik_56

Javascript

<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: 
");
    printDivisors(100);
     
// This code is contributed by simranarora5sos
 
</script>

Выход:

 Делители 100: 
1 2 4 5 10 20 25 50 100

Спасибо Mysterious Mind за предложение вышеупомянутого решения.

Эта статья предоставлена Ашутошем Кумаром. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Misc

Найти все делители натурального числа | Комплект 2

C++

Java

Python3

C#

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ