Given a positive integer ‘n’ and query ‘q’. Print all the divisors of number ‘n’.
Input: 6 Output: 1 2 3 6 Explanation Divisors of 6 are: 1, 2, 3, 6 Input: 10 Output: 1 2 5 10
Naive approach is to iterate through 1 to sqrt(n) for every query ‘q’ and print the divisors accordingly. See this to understand more. Time complexity of this approach is q*sqrt(n) which is not sufficient for large number of queries. Efficient approach is to use factorization by using sieve base approach.
- Create a list of consecutive integers from 1 to ‘n’.
- For any number ‘d’, iterate through all the multiples of ‘d’ i.e., d, 2d, 3d, … etc. Meanwhile push the divisor ‘d’ for every multiples.
C++
// C++ program to print divisors of// number for multiple query#include <iostream>#include <vector>using namespace std; const int MAX = 1e5; // Initialize global divisor vector// array of sequence containervector<int> divisor[MAX + 1]; // Sieve based approach to pre-// calculate all divisors of numbervoid sieve(){ for (int i = 1; i <= MAX; ++i) { for (int j = i; j <= MAX; j += i) divisor[j].push_back(i); }} // Utility function to print divisors// of given numberinline void printDivisor(int& n){ for (auto& div : divisor[n]) cout << div << " ";} // Driver codeint main(){ sieve(); int n = 10; cout << "Divisors of " << n << " = "; printDivisor(n); n = 30; cout << "\nDivisors of " << n << " = "; printDivisor(n); return 0;} |
Java
// Java program to print divisors of// number for multiple queryimport java.util.*;class GFG { static int MAX = 100000; // Initialize global divisor vector // array of sequence container static ArrayList<ArrayList<Integer> > divisor = new ArrayList<ArrayList<Integer> >(); // Sieve based approach to pre- // calculate all divisors of number static void sieve() { for (int i = 0; i <= MAX; i++) divisor.add(new ArrayList<Integer>()); for (int i = 1; i <= MAX; ++i) { for (int j = i; j <= MAX; j += i) divisor.get(j).add(i); } } // Utility function to print divisors // of given number static void printDivisor(int n) { for (int i = 0; i < divisor.get(n).size(); i++) System.out.print((divisor.get(n)).get(i) + " "); System.out.println(); } // Driver code public static void main(String[] args) { sieve(); int n = 10; System.out.println("Divisors of " + n + " = "); printDivisor(n); n = 30; System.out.println("Divisors of " + n + " = "); printDivisor(n); }}// This code is contributed by phasing17 |
Python3
# Python3 program to print divisors of# number for multiple queryMAX = 100000# Initialize global divisor vector# array of sequence containerdivisor = [list() for _ in range(MAX + 1)]# Sieve based approach to pre-# calculate all divisors of numberdef sieve(): for i in range(1, MAX + 1): for j in range(i, MAX + 1, i): divisor[j] = divisor[j] + [i]# Utility function to print divisors# of given numberdef printDivisor(n): print(*(divisor[n]))# Driver codesieve()n = 10print("Divisors of", n, "=")printDivisor(n)n = 30print("Divisors of", n, "=")printDivisor(n)# This code is contributed by phasing17 |
C#
// C# program to print divisors of// number for multiple queryusing System;using System.Collections.Generic;class GFG { static int MAX = 100000; // Initialize global divisor vector // array of sequence container static List<List<int> > divisor = new List<List<int> >(); // Sieve based approach to pre- // calculate all divisors of number static void sieve() { for (int i = 0; i <= MAX; i++) divisor.Add(new List<int>()); for (int i = 1; i <= MAX; ++i) { for (int j = i; j <= MAX; j += i) divisor[j].Add(i); } } // Utility function to print divisors // of given number static void printDivisor(int n) { foreach(var div in divisor[n]) Console.Write(div + " "); } // Driver code public static void Main(string[] args) { sieve(); int n = 10; Console.WriteLine("Divisors of " + n + " = "); printDivisor(n); n = 30; Console.WriteLine("Divisors of " + n + " = "); printDivisor(n); }}// This code is contributed by phasing17 |
Javascript
// JavaScript program to print divisors of// number for multiple querylet MAX = 1e5; // Initialize global divisor vector// array of sequence containerlet divisor = new Array(MAX + 1);for (var i = 1; i <= MAX; i++) divisor[i] = []; // Sieve based approach to pre-// calculate all divisors of numberfunction sieve(){ for (var i = 1; i <= MAX; ++i) { for (var j = i; j <= MAX; j += i) divisor[j].push(i); }} // Utility function to print divisors// of given numberfunction printDivisor(n){ for (var div of divisor[n]) process.stdout.write(div + " ");} // Driver codesieve(); let n = 10;console.log("Divisors of " + n + " = ");printDivisor(n); n = 30;console.log("\nDivisors of " + n + " = ");printDivisor(n);// This code is contributed by phasing17 |
Output
Divisors of 10 = 1 2 5 10
Divisors of 30 = 1 2 3 5 6 10 15 303
Time complexity: O(len) for each query, where len is equal to total divisors of number ‘n’.
Auxiliary space: O(MAX)
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!
