Рубрики

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

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

C / C ++

// C ++ реализация метода Naive для печати всех
// делители
#include <bits/stdc++.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 реализация метода Naive для печати всех
// делители

  

class Test

{

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

    static void printDivisors(int n)

    {

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

            if (n%i==0)

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

    }

  

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

    public static void main(String args[])

    {

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

        printDivisors(100);;

    }

}

питон

# Python реализация метода Naive
# распечатать все делители

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

def printDivisors(n) :

    i = 1

    while i <= n :

        if (n % i==0) :

            print i,

        i = i + 1

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

print "The divisors of 100 are: "

printDivisors(100)

  
# Этот код предоставлен Никитой Тивари.

C #

// 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
// PHP реализация Naive
// метод для печати всех делителей

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

function printDivisors($n)

{

    for ($i = 1; $i <= $n; $i++)

        if ($n % $i == 0)

            echo $i," ";

}

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

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

printDivisors(100);

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

Выход :

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

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

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

Используя этот факт, мы могли бы значительно ускорить нашу программу.
Мы, однако, должны быть осторожны, если есть два равных делителя, как в случае (10, 10). В таком случае мы напечатали бы только один из них.

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

C / C ++

// Лучшее (чем наивное) решение, чтобы найти все делители
#include <bits/stdc++.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;

}

Джава

// Лучшее (чем наивное) решение, чтобы найти все делители

  

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.printf("%d ", i);

       

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

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

            }

        }

    }

  

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

    public static void main(String args[])

    {

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

        printDivisors(100);;

    }

}

питон

# Лучшее (чем наивное) решение, чтобы найти все делители

import math 

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

def printDivisors(n) :

      

    # Обратите внимание, что этот цикл работает до квадратного корня

    i = 1

    while i <= math.sqrt(n):

          

        if (n % i == 0) :

              

            # Если делители равны, выведите только один

            if (n / i == i) :

                print i,

            else :

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

                print i , n/i,

        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);

    }

}

  
// Этот код предоставлен Smitha

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);

      
// Этот код предоставлен anuj_67.

  

  
?>


Выход :

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

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

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

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

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

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

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

0.00 (0%) 0 votes