Consultas para imprimir todos los divisores de número

Dado un entero positivo ‘n’ y consulta ‘q’. Imprime todos los divisores del número ‘n’.

Input: 6
Output: 1 2 3 6
Explanation
Divisors of 6 are: 1, 2, 3, 6

Input: 10
Output: 1 2 5 10

El enfoque ingenuo es iterar a través de 1 a sqrt (n) para cada consulta ‘q’ e imprimir los divisores en consecuencia. Mira esto para entender más. La complejidad temporal de este enfoque es q*sqrt(n), que no es suficiente para un gran número de consultas. El enfoque eficiente es utilizar la factorización utilizando el enfoque de base de tamiz .

• Cree una lista de enteros consecutivos del 1 al ‘n’.
• Para cualquier número ‘d’, repita todos los múltiplos de ‘d’, es decir, d, 2d, 3d, … etc. Mientras tanto, empuje el divisor ‘d’ para cada múltiplo.

// 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 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 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# 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 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

Salida 
Divisores de 10 = 1 2 5 10 
Divisores de 30 = 1 2 3 5 6 10 15 303

Complejidad de tiempo: O(len) para cada consulta, donde len es igual a los divisores totales del número ‘n’.
Espacio auxiliar: O(MAX)