Найти все делители натурального числа | Комплект 1
Для натурального числа 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.