Queries to print all divisors of number

0 0 4 minutes read

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 container
vector<int> divisor[MAX + 1];
   
// Sieve based approach to pre-
// calculate all divisors of number
void 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 number
inline void printDivisor(int& n)
{
    for (auto& div : divisor[n])
        cout << div << " ";
}
   
// Driver code
int 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 query
 
import 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 query
 
MAX = 100000
 
# Initialize global divisor vector
# array of sequence container
divisor = [list() for _ in range(MAX + 1)]
 
# Sieve based approach to pre-
# calculate all divisors of number
def 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 number
def printDivisor(n):
    print(*(divisor[n]))
 
 
# Driver code
sieve()
 
n = 10
print("Divisors of", n, "=")
printDivisor(n)
 
n = 30
print("Divisors of", n, "=")
printDivisor(n)
 
# This code is contributed by phasing17

C#

// C# program to print divisors of
// number for multiple query
 
using 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 query
let MAX = 1e5;
   
// Initialize global divisor vector
// array of sequence container
let divisor = new Array(MAX + 1);
for (var i = 1; i <= MAX; i++)
    divisor[i] = [];
   
// Sieve based approach to pre-
// calculate all divisors of number
function 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 number
function printDivisor(n)
{
    for (var div of divisor[n])
        process.stdout.write(div + " ");
}
   
// Driver code
sieve();
   
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)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!