Рубрики

Найти все делители натурального числа | Набор 2

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

Примеры:

 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 

Мы настоятельно рекомендуем ссылаться на приведенную ниже статью в качестве обязательного условия.
Найти все делители натурального числа | Комплект 1

В приведенном выше сообщении мы нашли способ найти все делители в O (sqrt (n)).

Однако, есть еще небольшая проблема в решении, вы можете догадаться?
Да! результат не в том порядке, который мы получили, используя метод грубой силы.

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

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

C ++

// AO (sqrt (n)) программа, которая печатает все делители
// в отсортированном порядке
#include <bits/stdc++.h>

using namespace std;

  
// функция для печати делителей

void printDivisors(int n)

{

    // Вектор для хранения половины делителей

    vector<int> v;

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

    {

        if (n%i==0)

        {

            if (n/i == i) // проверяем равны ли делители

                printf("%d ", i);

            else

            {

                printf("%d ", i);

  

                // вставляем второй делитель в векторе

                v.push_back(n/i);

            }

        }

    }

  

    // вектор будет напечатан в обратном порядке

    for (int i=v.size()-1; i>=0; i--)

        printf("%d ", v[i]);

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

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

    printDivisors(100);

    return 0;

}

Джава

// AO (sqrt (n)) Java-программа, которая печатает все делители
// в отсортированном порядке

  

import java.util.Vector;

  

class Test

{

    // метод для печати делителей

    static void printDivisors(int n)

    {

        // Вектор для хранения половины делителей

        Vector<Integer> v = new Vector<>();

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

        {

            if (n%i==0)

            {

                if (n/i == i) // проверяем равны ли делители

                    System.out.printf("%d ", i);

                else

                {

                     System.out.printf("%d ", i);

       

                    // вставляем второй делитель в векторе

                    v.add(n/i);

                }

            }

        }

       

        // вектор будет напечатан в обратном порядке

        for (int i=v.size()-1; i>=0; i--)

             System.out.printf("%d ", v.get(i));

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

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

        printDivisors(100);

    }

}

python3

# AO (sqrt (n)) Java-программа, которая печатает
# все делители в отсортированном порядке

import math 

  
# Способ печати делителей

def printDivisors(n) :

    list = [] 

      

    # Список для хранения половины делителей

    for i in range(1, int(math.sqrt(n) + 1)) :

          

        if (n % i == 0) :

              

            # Проверьте, равны ли делители

            if (n / i == i) :

                print (i, end=" ")

            else :

                # В противном случае выведите оба

                print (i, end=" ")

                list.append(int(n / i))

                  

    # Список будет напечатан в обратном порядке

    for i in list[::-1] :

        print (i, end=" ")

          
# Метод драйвера

print ("The divisors of 100 are: ")

printDivisors(100)

  
# Этот код предоставлен Gitanjali

C #

// AO (sqrt (n)) C # программа, которая
// печатает все делители в отсортированном порядке

using System;

  

class GFG

{
// метод для печати делителей

static void printDivisors(int n)

{

    // Вектор для хранения половины

    // делителей

    int[] v = new int[n];

    int t = 0;

    for (int i = 1; 

             i <= Math.Sqrt(n); i++)

    {

        if (n % i == 0)

        {

            // проверяем равны ли делители

            if (n / i == i) 

                Console.Write(i + " ");

            else

            {

                Console.Write(i + " ");

  

                // толкаем второй делитель

                // в векторе

                v[t++] = n / i;

            }

        }

    }

  

    // Вектор будет

    // печатается в обратном порядке

    for (int i = t - 1; i >= 0; i--)

        Console.Write(v[i] + " ");

}

  
// Код драйвера

public static void Main()

{

    Console.Write("The divisors of 100 are: \n");

    printDivisors(100);

}
}

  
// Этот код добавлен
// ChitraNayal

PHP

<?php
// AO (sqrt (n)) программа, которая
// печатает все делители в
// отсортированный порядок

  
// функция для печати
// делители

function printDivisors($n)

{

    // Вектор для хранения половины

    // делителей

    $v;

    $t = 0;

    for ($i = 1; 

         $i <= (int)sqrt($n); $i++)

    {

        if ($n % $i == 0)

        {

            // проверяем равны ли делители

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

                echo $i . " ";

            else

            {

                echo $i . " ";

  

                // толкаем вторую

                // делитель в векторе

                $v[$t++] = (int)$n / $i;

            }

        }

    }

  

    // Вектор будет

    // печатается в обратном порядке

    for ($i = count($v) - 1; 

         $i >= 0; $i--)

        echo $v[$i] . " ";

}

  
// Код драйвера

echo "The divisors of 100 are: \n";

printDivisors(100);

  
// Этот код предоставлен mits
?>


Выход :

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

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

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

Рекомендуемые посты:

Найти все делители натурального числа | Набор 2

0.00 (0%) 0 votes