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

Опубликовано: 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 до n, проверить, делит ли это число n, и распечатать его. Ниже приведена программа для того же:

Выход:

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

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

Можем ли мы улучшить вышеуказанное решение?
Если присмотреться, все делители попарно присутствуют. Например, если n = 100, то различные пары делителей: (1,100), (2,50), (4,25), (5,20), (10,10)
Используя этот факт, мы могли бы значительно ускорить нашу программу.
Однако нужно быть осторожным, если есть два равных делителя, как в случае (10, 10). В таком случае мы напечатаем только один из них.

Below is an implementation for the same:

C++

// A Better (than Naive) Solution to find all divisiors
#include <bits/stdc++.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: 
");
    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);;
    }
}

Python

# A Better (than Naive) Solution to find all divisiors
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,
            else :
                # Otherwise print both
                print i , n/i,
        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: 
");
        printDivisors(100);
    }
}
 
// This code is contributed by Smitha

PHP

<?php
// A Better (than Naive) Solution
// to find all divisiors
 
// 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: 
";
    printDivisors(100);
     
// This code is contributed by anuj_67.
 
 
?>

Javascript

<script>
 
// A Better (than Naive) Solution to find all divisiors
 
// 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>

Выход:

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

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

Однако в решении все еще есть небольшая проблема, вы можете догадаться?
Да! вывод не отсортирован, как мы получили с помощью техники грубой силы. Ниже приведено решение для времени O (sqrt (n)), которое выводит делители в отсортированном порядке.
Найти все делители натурального числа | Комплект 2
Эта статья предоставлена Ашутошем Кумаром. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

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

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

Misc

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

C++

Java

Python

C#

PHP

Javascript

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