Given a natural number n, print all distinct divisors of it.
Examples:
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
We strongly recommend referring to the below article as a prerequisite.
Find all divisors of a natural number | Set 1
In the above post, we found a way to find all the divisors in O(sqrt(n)).
However there is still a minor problem with the solution, can you guess?
Yes! the output is not in a sorted fashion which we had got using the brute-force technique.
How to print the output in sorted order?
If we observe the output which we had got, we can analyze that the divisors are printed in a zig-zag fashion (small, large pairs). Hence, if we store half of them, we can print them in sorted order.
Algorithm:
- Define a method named “printDivisors” with a void return type that takes an integer value as an input variable.
- Initialize a Vector “v” to store half of the divisors.
- Start a for loop and iterate through all the numbers from 1 to the square root of “n”.
- now, inside the loop Check if the remainder of “n” divided by the current iteration variable “i” is 0. If true, then proceed to the next step:
- Check if the divisors are equal by comparing “n/i” and “i”. If equal, then print the divisor “i”
- Otherwise, print the divisor “i” and add “n/i” to the vector “v”.
- now, inside the loop Check if the remainder of “n” divided by the current iteration variable “i” is 0. If true, then proceed to the next step:
- Now start another for loop and iterate through the vector “v” in reverse order and print each element.
Below is an implementation for the same:
C++
// A O(sqrt(n)) program that prints all divisors// in sorted order#include <bits/stdc++.h>using namespace std;// function to print the divisorsvoid printDivisors(int n){ // Vector to store half of the divisors vector<int> v; for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { // check if divisors are equal if (n / i == i) printf("%d ", i); else { printf("%d ", i); // push the second divisor in the vector v.push_back(n / i); } } } // The vector will be printed in reverse for (int i = v.size() - 1; i >= 0; i--) printf("%d ", v[i]);}/* Driver program to test above function */int main(){ printf("The divisors of 100 are: \n"); printDivisors(100); return 0;} |
Java
// A O(sqrt(n)) java program that prints all divisors// in sorted orderimport java.util.Vector;class Test { // method to print the divisors static void printDivisors(int n) { // Vector to store half of the divisors Vector<Integer> v = new Vector<>(); for (int i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { // check if divisors are equal if (n / i == i) System.out.printf("%d ", i); else { System.out.printf("%d ", i); // push the second divisor in the vector v.add(n / i); } } } // The vector will be printed in reverse for (int i = v.size() - 1; i >= 0; i--) System.out.printf("%d ", v.get(i)); } // Driver method public static void main(String args[]) { System.out.println("The divisors of 100 are: "); printDivisors(100); }} |
Python3
# A O(sqrt(n)) java program that prints# all divisors in sorted orderimport math# Method to print the divisorsdef printDivisors(n): list = [] # List to store half of the divisors for i in range(1, int(math.sqrt(n) + 1)): if (n % i == 0): # Check if divisors are equal if (n / i == i): print(i, end=" ") else: # Otherwise print both print(i, end=" ") list.append(int(n / i)) # The list will be printed in reverse for i in list[::-1]: print(i, end=" ")# Driver methodprint("The divisors of 100 are: ")printDivisors(100)# This code is contributed by Gitanjali |
C#
// A O(sqrt(n)) C# program that// prints all divisors in sorted orderusing System;class GFG { // method to print the divisors static void printDivisors(int n) { // Vector to store half // of the divisors int[] v = new int[n]; int t = 0; for (int i = 1; i <= Math.Sqrt(n); i++) { if (n % i == 0) { // check if divisors are equal if (n / i == i) Console.Write(i + " "); else { Console.Write(i + " "); // push the second divisor // in the vector v[t++] = n / i; } } } // The vector will be // printed in reverse for (int i = t - 1; i >= 0; i--) Console.Write(v[i] + " "); } // Driver Code public static void Main() { Console.Write("The divisors of 100 are: \n"); printDivisors(100); }}// This code is contributed// by ChitraNayal |
PHP
<?php// A O(sqrt(n)) program that // prints all divisors in// sorted order// function to print// the divisorsfunction printDivisors($n){ // Vector to store half // of the divisors $v; $t = 0; for ($i = 1; $i <= (int)sqrt($n); $i++) { if ($n % $i == 0) { // check if divisors are equal if ((int)$n / $i == $i) echo $i . " "; else { echo $i . " "; // push the second // divisor in the vector $v[$t++] = (int)$n / $i; } } } // The vector will be // printed in reverse for ($i = count($v) - 1; $i >= 0; $i--) echo $v[$i] . " ";}// Driver codeecho "The divisors of 100 are: \n";printDivisors(100);// This code is contributed by mits?> |
Javascript
<script>// A O(sqrt(n)) program that // prints all divisors in// sorted order// function to print// the divisorsfunction printDivisors(n){ // Vector to store half // of the divisors let v = []; let t = 0; for (let i = 1; i <= parseInt(Math.sqrt(n)); i++) { if (n % i == 0) { // check if divisors are equal if (parseInt(n / i) == i) document.write(i + " "); else { document.write(i + " "); // push the second // divisor in the vector v[t++] = parseInt(n / i); } } } // The vector will be // printed in reverse for (let i = v.length - 1; i >= 0; i--){ document.write(v[i] + " "); }}// Driver codedocument.write("The divisors of 100 are: \n");printDivisors(100);// This code is contributed by _saurabh_jaiswal</script> |
Output
The divisors of 100 are: 1 2 4 5 10 20 25 50 100
Time Complexity : O(sqrt(n))
Auxiliary Space : O(sqrt(n))
Method 2 :
Approach: In the below approach using for loop we are first printing the numbers only which gives the remainder as 0 and once we break the loop we are just printing the quotient of numbers which gives the remainder as 0.
Let’s understand through an example :
n = 10
from 1 to 10
keep checking n % 1 == 0 print 1
n % 2 == 0 print 2
3, 4, 5, 6, 7, 8, 9 will not give remainder 0
exit loop;
The 1 and 2 which gives remainder as 0 it also mean that n is perfectly divisible by 1 and 2 so in second for loop keep printing the quotient on dividing by 1 and 2 which left remainder 0
from 10 to 1
keep checking n % 1 == 0 print n/1
n % 2 == 0 print n/2
exit loop
C++
// A O(sqrt(n)) program that prints all divisors// in sorted order#include <iostream>#include <math.h>using namespace std;// Function to print the divisorsvoid printDivisors(int n){ int i; for (i = 1; i * i < n; i++) { if (n % i == 0) cout<<i<<" "; } if (i - (n / i) == 1) { i--; } for (; i >= 1; i--) { if (n % i == 0) cout<<n / i<<" "; }}// Driver codeint main(){ cout << "The divisors of 100 are: \n"; printDivisors(100); return 0;}// This code is contributed by siteshbiswal |
C
// A O(sqrt(n)) program that prints all divisors// in sorted order#include <stdio.h>#include <math.h>// function to print the divisorsvoid printDivisors(int n){ int i; for ( i = 1; i*i < n; i++) { if (n % i == 0) printf("%d ", i); } if(i-(n/i)==1) { i--; } for (; 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: \n"); 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) { int i; for( i = 1; i * i < n; i++) { if (n % i == 0) System.out.print(i + " "); } if(i-(n/i)==1) { i--; } for(; i >= 1; i--) { if (n % i == 0) System.out.print(n / i + " "); } } // Driver codepublic static void main(String[] args) { System.out.println("The divisors of 100 are: "); printDivisors(100); }}// This code is contributed by Prakash Veer Singh Tomar. |
Python3
# A O(sqrt(n)) program that prints all divisors # in sorted orderfrom math import *# Function to print the divisorsdef 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 Codeprint("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 orderusing 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: \n"); 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 divisorsfunction 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: \n"); printDivisors(100); // This code is contributed by simranarora5sos </script> |
Output
The divisors of 100 are: 1 2 4 5 10 20 25 50 100
Time complexity : O(sqrt(n))
Auxiliary Space : O(1)
Thanks to Mysterious Mind for suggesting the above solution.
The if condition between the two loops is used when corner factors in the loop’s condition have a difference of 1(for example- factors of 30 (5,6) here, 5 will be printed two times; to resolve that issue this step is required.
This article is contributed by Ashutosh Kumar. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
