Dadas consultas Q, de tipo: LR , para cada consulta debe imprimir el número máximo de divisores que tiene un número x (L <= x <= R) .
Ejemplos:
L = 1 R = 10:
1 has 1 divisor.
2 has 2 divisors.
3 has 2 divisors.
4 has 3 divisors.
5 has 2 divisors.
6 has 4 divisors.
7 has 2 divisors.
8 has 4 divisors.
9 has 3 divisors.
10 has 4 divisors.
So the answer for above query is 4, as it is the maximum number of
divisors a number has in [1, 10].
Requisitos previos: tamiz de Eratóstenes , árbol de segmentos
A continuación se muestran los pasos para resolver el problema.
- En primer lugar, veamos cuántos números de divisores tiene un número n = p 1 k 1 * p 2 k 2 * … * p n k n (donde p 1 , p 2 , …, p n son números primos) tiene; la respuesta es (k 1 + 1)*(k 2 + 1)*…*(k n + 1) . ¿Cómo? Para cada número primo en la descomposición en factores primos, podemos tener sus k i + 1 posibles potencias en un divisor (0, 1, 2,…, k i ).
- Ahora veamos cómo podemos encontrar la descomposición en factores primos de un número, primero construimos una array, small_prime[] , que almacena el divisor primo más pequeño de i en el i -ésimo índice, dividimos un número por su divisor primo más pequeño para obtener un nuevo (también tenemos almacenado el divisor primo más pequeño de este nuevo número), seguimos haciéndolo hasta que cambia el primo más pequeño del número, cuando el factor primo más pequeño del nuevo número es diferente del número anterior, tenemos k i para el i -ésimo número primo en la descomposición en factores primos del número dado.
- Finalmente, obtenemos el número de divisores para todos los números y los almacenamos en un árbol de segmentos que mantiene los números máximos en los segmentos. Respondemos a cada consulta consultando el árbol de segmentos.
C++
// A C++ implementation of the above idea to process
// queries of finding a number with maximum divisors.
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define INF 99999999
int smallest_prime[maxn];
int divisors[maxn];
int segmentTree[4 * maxn];
// Finds smallest prime factor of all numbers in
// range[1, maxn) and stores them in smallest_prime[],
// smallest_prime[i] should contain the smallest prime
// that divides i
void findSmallestPrimeFactors()
{
// Initialize the smallest_prime factors of all
// to infinity
for (int i = 0 ; i < maxn ; i ++ )
smallest_prime[i] = INF;
// to be built like eratosthenes sieve
for (long long i = 2; i < maxn; i++)
{
if (smallest_prime[i] == INF)
{
// prime number will have its smallest_prime
// equal to itself
smallest_prime[i] = i;
for (long long j = i * i; j < maxn; j += i)
// if 'i' is the first prime number reaching 'j'
if (smallest_prime[j] > i)
smallest_prime[j] = i;
}
}
}
// number of divisors of n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn)
// are equal to (k1+1) * (k2+1) ... (kn+1)
// this function finds the number of divisors of all numbers
// in range [1, maxn) and stores it in divisors[]
// divisors[i] stores the number of divisors i has
void buildDivisorsArray()
{
for (int i = 1; i < maxn; i++)
{
divisors[i] = 1;
int n = i, p = smallest_prime[i], k = 0;
// we can obtain the prime factorization of the number n
// n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn) using the
// smallest_prime[] array, we keep dividing n by its
// smallest_prime until it becomes 1, whilst we check
// if we have need to set k zero
while (n > 1)
{
n = n / p;
k ++;
if (smallest_prime[n] != p)
{
//use p^k, initialize k to 0
divisors[i] = divisors[i] * (k + 1);
k = 0;
}
p = smallest_prime[n];
}
}
}
// builds segment tree for divisors[] array
void buildSegtmentTree(int node, int a, int b)
{
// leaf node
if (a == b)
{
segmentTree[node] = divisors[a];
return ;
}
//build left and right subtree
buildSegtmentTree(2 * node, a, (a + b) / 2);
buildSegtmentTree(2 * node + 1, ((a + b) / 2) + 1, b);
//combine the information from left
//and right subtree at current node
segmentTree[node] = max(segmentTree[2 * node],
segmentTree[2 *node + 1]);
}
//returns the maximum number of divisors in [l, r]
int query(int node, int a, int b, int l, int r)
{
// If current node's range is disjoint with query range
if (l > b || a > r)
return -1;
// If the current node stores information for the range
// that is completely inside the query range
if (a >= l && b <= r)
return segmentTree[node];
// Returns maximum number of divisors from left
// or right subtree
return max(query(2 * node, a, (a + b) / 2, l, r),
query(2 * node + 1, ((a + b) / 2) + 1, b,l,r));
}
// driver code
int main()
{
// First find smallest prime divisors for all
// the numbers
findSmallestPrimeFactors();
// Then build the divisors[] array to store
// the number of divisors
buildDivisorsArray();
// Build segment tree for the divisors[] array
buildSegtmentTree(1, 1, maxn - 1);
cout << "Maximum divisors that a number has "
<< " in [1, 100] are "
<< query(1, 1, maxn - 1, 1, 100) << endl;
cout << "Maximum divisors that a number has"
<< " in [10, 48] are "
<< query(1, 1, maxn - 1, 10, 48) << endl;
cout << "Maximum divisors that a number has"
<< " in [1, 10] are "
<< query(1, 1, maxn - 1, 1, 10) << endl;
return 0;
}
Java
// Java implementation of the above idea to process
// queries of finding a number with maximum divisors.
import java.util.*;
class GFG
{
static int maxn = 10005;
static int INF = 999999;
static int []smallest_prime = new int[maxn];
static int []divisors = new int[maxn];
static int []segmentTree = new int[4 * maxn];
// Finds smallest prime factor of all numbers
// in range[1, maxn) and stores them in
// smallest_prime[], smallest_prime[i] should
// contain the smallest prime that divides i
static void findSmallestPrimeFactors()
{
// Initialize the smallest_prime factors
// of all to infinity
for (int i = 0 ; i < maxn ; i ++ )
smallest_prime[i] = INF;
// to be built like eratosthenes sieve
for (int i = 2; i < maxn; i++)
{
if (smallest_prime[i] == INF)
{
// prime number will have its
// smallest_prime equal to itself
smallest_prime[i] = i;
for (int j = i * i; j < maxn; j += i)
// if 'i' is the first
// prime number reaching 'j'
if (smallest_prime[j] > i)
smallest_prime[j] = i;
}
}
}
// number of divisors of n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn)
// are equal to (k1+1) * (k2+1) ... (kn+1)
// this function finds the number of divisors of all numbers
// in range [1, maxn) and stores it in divisors[]
// divisors[i] stores the number of divisors i has
static void buildDivisorsArray()
{
for (int i = 1; i < maxn; i++)
{
divisors[i] = 1;
int n = i, p = smallest_prime[i], k = 0;
// we can obtain the prime factorization of
// the number n, n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn)
// using the smallest_prime[] array, we keep dividing n
// by its smallest_prime until it becomes 1,
// whilst we check if we have need to set k zero
while (n > 1)
{
n = n / p;
k ++;
if (smallest_prime[n] != p)
{
// use p^k, initialize k to 0
divisors[i] = divisors[i] * (k + 1);
k = 0;
}
p = smallest_prime[n];
}
}
}
// builds segment tree for divisors[] array
static void buildSegtmentTree(int node, int a, int b)
{
// leaf node
if (a == b)
{
segmentTree[node] = divisors[a];
return ;
}
//build left and right subtree
buildSegtmentTree(2 * node, a, (a + b) / 2);
buildSegtmentTree(2 * node + 1, ((a + b) / 2) + 1, b);
//combine the information from left
//and right subtree at current node
segmentTree[node] = Math.max(segmentTree[2 * node],
segmentTree[2 *node + 1]);
}
// returns the maximum number of divisors in [l, r]
static int query(int node, int a, int b, int l, int r)
{
// If current node's range is disjoint
// with query range
if (l > b || a > r)
return -1;
// If the current node stores information
// for the range that is completely inside
// the query range
if (a >= l && b <= r)
return segmentTree[node];
// Returns maximum number of divisors from left
// or right subtree
return Math.max(query(2 * node, a, (a + b) / 2, l, r),
query(2 * node + 1,
((a + b) / 2) + 1, b, l, r));
}
// Driver Code
public static void main(String[] args)
{
// First find smallest prime divisors
// for all the numbers
findSmallestPrimeFactors();
// Then build the divisors[] array to store
// the number of divisors
buildDivisorsArray();
// Build segment tree for the divisors[] array
buildSegtmentTree(1, 1, maxn - 1);
System.out.println("Maximum divisors that a number " +
"has in [1, 100] are " +
query(1, 1, maxn - 1, 1, 100));
System.out.println("Maximum divisors that a number " +
"has in [10, 48] are " +
query(1, 1, maxn - 1, 10, 48));
System.out.println("Maximum divisors that a number " +
"has in [1, 10] are " +
query(1, 1, maxn - 1, 1, 10));
}
}
// This code is contributed by PrinciRaj1992
Python 3
# Python 3 implementation of the above
# idea to process queries of finding a
# number with maximum divisors.
maxn = 1000005
INF = 99999999
smallest_prime = [0] * maxn
divisors = [0] * maxn
segmentTree = [0] * (4 * maxn)
# Finds smallest prime factor of all
# numbers in range[1, maxn) and stores
# them in smallest_prime[], smallest_prime[i]
# should contain the smallest prime that divides i
def findSmallestPrimeFactors():
# Initialize the smallest_prime
# factors of all to infinity
for i in range(maxn ):
smallest_prime[i] = INF
# to be built like eratosthenes sieve
for i in range(2, maxn):
if (smallest_prime[i] == INF):
# prime number will have its
# smallest_prime equal to itself
smallest_prime[i] = i
for j in range(i * i, maxn , i):
# if 'i' is the first prime
# number reaching 'j'
if (smallest_prime[j] > i):
smallest_prime[j] = i
# number of divisors of n = (p1 ^ k1) *
# (p2 ^ k2) ... (pn ^ kn) are equal to
# (k1+1) * (k2+1) ... (kn+1). This function
# finds the number of divisors of all numbers
# in range [1, maxn) and stores it in divisors[]
# divisors[i] stores the number of divisors i has
def buildDivisorsArray():
for i in range(1, maxn):
divisors[i] = 1
n = i
p = smallest_prime[i]
k = 0
# we can obtain the prime factorization
# of the number n n = (p1 ^ k1) * (p2 ^ k2)
# ... (pn ^ kn) using the smallest_prime[]
# array, we keep dividing n by its
# smallest_prime until it becomes 1, whilst
# we check if we have need to set k zero
while (n > 1):
n = n // p
k += 1
if (smallest_prime[n] != p):
# use p^k, initialize k to 0
divisors[i] = divisors[i] * (k + 1)
k = 0
p = smallest_prime[n]
# builds segment tree for divisors[] array
def buildSegtmentTree( node, a, b):
# leaf node
if (a == b):
segmentTree[node] = divisors[a]
return
#build left and right subtree
buildSegtmentTree(2 * node, a, (a + b) // 2)
buildSegtmentTree(2 * node + 1,
((a + b) // 2) + 1, b)
#combine the information from left
#and right subtree at current node
segmentTree[node] = max(segmentTree[2 * node],
segmentTree[2 * node + 1])
# returns the maximum number of
# divisors in [l, r]
def query(node, a, b, l, r):
# If current node's range is disjoint
# with query range
if (l > b or a > r):
return -1
# If the current node stores information
# for the range that is completely inside
# the query range
if (a >= l and b <= r):
return segmentTree[node]
# Returns maximum number of divisors
# from left or right subtree
return max(query(2 * node, a, (a + b) // 2, l, r),
query(2 * node + 1,
((a + b) // 2) + 1, b, l, r))
# Driver code
if __name__ == "__main__":
# First find smallest prime divisors
# for all the numbers
findSmallestPrimeFactors()
# Then build the divisors[] array to
# store the number of divisors
buildDivisorsArray()
# Build segment tree for the divisors[] array
buildSegtmentTree(1, 1, maxn - 1)
print("Maximum divisors that a number has ",
" in [1, 100] are ",
query(1, 1, maxn - 1, 1, 100))
print("Maximum divisors that a number has",
" in [10, 48] are ",
query(1, 1, maxn - 1, 10, 48))
print( "Maximum divisors that a number has",
" in [1, 10] are ",
query(1, 1, maxn - 1, 1, 10))
# This code is contributed by ita_c
C#
// C# implementation of the above idea
// to process queries of finding a number
// with maximum divisors.
using System;
class GFG
{
static int maxn = 10005;
static int INF = 999999;
static int []smallest_prime = new int[maxn];
static int []divisors = new int[maxn];
static int []segmentTree = new int[4 * maxn];
// Finds smallest prime factor of all numbers
// in range[1, maxn) and stores them in
// smallest_prime[], smallest_prime[i] should
// contain the smallest prime that divides i
static void findSmallestPrimeFactors()
{
// Initialize the smallest_prime
// factors of all to infinity
for (int i = 0 ; i < maxn ; i ++ )
smallest_prime[i] = INF;
// to be built like eratosthenes sieve
for (int i = 2; i < maxn; i++)
{
if (smallest_prime[i] == INF)
{
// prime number will have its
// smallest_prime equal to itself
smallest_prime[i] = i;
for (int j = i * i; j < maxn; j += i)
// if 'i' is the first
// prime number reaching 'j'
if (smallest_prime[j] > i)
smallest_prime[j] = i;
}
}
}
// number of divisors of
// n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn)
// are equal to (k1+1) * (k2+1) ... (kn+1)
// this function finds the number of divisors
// of all numbers in range [1, maxn) and stores
// it in divisors[] divisors[i] stores the
// number of divisors i has
static void buildDivisorsArray()
{
for (int i = 1; i < maxn; i++)
{
divisors[i] = 1;
int n = i, p = smallest_prime[i], k = 0;
// we can obtain the prime factorization of
// the number n,
// n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn)
// using the smallest_prime[] array,
// we keep dividing n by its smallest_prime
// until it becomes 1, whilst we check if
// we have need to set k zero
while (n > 1)
{
n = n / p;
k ++;
if (smallest_prime[n] != p)
{
// use p^k, initialize k to 0
divisors[i] = divisors[i] * (k + 1);
k = 0;
}
p = smallest_prime[n];
}
}
}
// builds segment tree for divisors[] array
static void buildSegtmentTree(int node,
int a, int b)
{
// leaf node
if (a == b)
{
segmentTree[node] = divisors[a];
return;
}
//build left and right subtree
buildSegtmentTree(2 * node, a, (a + b) / 2);
buildSegtmentTree(2 * node + 1,
((a + b) / 2) + 1, b);
//combine the information from left
//and right subtree at current node
segmentTree[node] = Math.Max(segmentTree[2 * node],
segmentTree[2 *node + 1]);
}
// returns the maximum number of divisors in [l, r]
static int query(int node, int a, int b, int l, int r)
{
// If current node's range is disjoint
// with query range
if (l > b || a > r)
return -1;
// If the current node stores information
// for the range that is completely inside
// the query range
if (a >= l && b <= r)
return segmentTree[node];
// Returns maximum number of divisors from left
// or right subtree
return Math.Max(query(2 * node, a, (a + b) / 2, l, r),
query(2 * node + 1,
((a + b) / 2) + 1, b, l, r));
}
// Driver Code
public static void Main(String[] args)
{
// First find smallest prime divisors
// for all the numbers
findSmallestPrimeFactors();
// Then build the divisors[] array
// to store the number of divisors
buildDivisorsArray();
// Build segment tree for the divisors[] array
buildSegtmentTree(1, 1, maxn - 1);
Console.WriteLine("Maximum divisors that a number " +
"has in [1, 100] are " +
query(1, 1, maxn - 1, 1, 100));
Console.WriteLine("Maximum divisors that a number " +
"has in [10, 48] are " +
query(1, 1, maxn - 1, 10, 48));
Console.WriteLine("Maximum divisors that a number " +
"has in [1, 10] are " +
query(1, 1, maxn - 1, 1, 10));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the above idea to process
// queries of finding a number with maximum divisors.
let maxn = 10005;
let INF = 999999;
let smallest_prime = new Array(maxn);
for(let i=0;i<maxn;i++)
{
smallest_prime[i]=0;
}
let divisors = new Array(maxn);
for(let i=0;i<maxn;i++)
{
divisors[i]=0;
}
let segmentTree = new Array(4 * maxn);
for(let i=0;i<4*maxn;i++)
{
segmentTree[i]=0;
}
// Finds smallest prime factor of all numbers
// in range[1, maxn) and stores them in
// smallest_prime[], smallest_prime[i] should
// contain the smallest prime that divides i
function findSmallestPrimeFactors()
{
// Initialize the smallest_prime factors
// of all to infinity
for (let i = 0 ; i < maxn ; i ++ )
smallest_prime[i] = INF;
// to be built like eratosthenes sieve
for (let i = 2; i < maxn; i++)
{
if (smallest_prime[i] == INF)
{
// prime number will have its
// smallest_prime equal to itself
smallest_prime[i] = i;
for (let j = i * i; j < maxn; j += i)
{
// if 'i' is the first
// prime number reaching 'j'
if (smallest_prime[j] > i)
smallest_prime[j] = i;
}
}
}
}
// number of divisors of n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn)
// are equal to (k1+1) * (k2+1) ... (kn+1)
// this function finds the number of divisors of all numbers
// in range [1, maxn) and stores it in divisors[]
// divisors[i] stores the number of divisors i has
function buildDivisorsArray()
{
for (let i = 1; i < maxn; i++)
{
divisors[i] = 1;
let n = i;
let p = smallest_prime[i]
let k = 0;
// we can obtain the prime factorization of
// the number n, n = (p1 ^ k1) * (p2 ^ k2) ... (pn ^ kn)
// using the smallest_prime[] array, we keep dividing n
// by its smallest_prime until it becomes 1,
// whilst we check if we have need to set k zero
while (n > 1)
{
n = Math.floor(n / p);
k++;
if (smallest_prime[n] != p)
{
// use p^k, initialize k to 0
divisors[i] = divisors[i] * (k + 1);
k = 0;
}
p = smallest_prime[n];
}
}
}
// builds segment tree for divisors[] array
function buildSegtmentTree(node,a,b)
{
// leaf node
if (a == b)
{
segmentTree[node] = divisors[a];
return ;
}
//build left and right subtree
buildSegtmentTree(2 * node, a, Math.floor((a + b) / 2));
buildSegtmentTree((2 * node) + 1, Math.floor((a + b) / 2) + 1, b);
//combine the information from left
//and right subtree at current node
segmentTree[node] = Math.max(segmentTree[2 * node],
segmentTree[(2 *node) + 1]);
}
// returns the maximum number of divisors in [l, r]
function query(node,a,b,l,r)
{
// If current node's range is disjoint
// with query range
if (l > b || a > r)
return -1;
// If the current node stores information
// for the range that is completely inside
// the query range
if (a >= l && b <= r)
return segmentTree[node];
// Returns maximum number of divisors from left
// or right subtree
return Math.max(query(2 * node, a,
Math.floor((a + b) / 2), l, r),
query(2 * node + 1,
Math.floor((a + b) / 2) + 1, b, l, r));
}
// Driver Code
// First find smallest prime divisors
// for all the numbers
findSmallestPrimeFactors();
// Then build the divisors[] array to store
// the number of divisors
buildDivisorsArray();
// Build segment tree for the divisors[] array
buildSegtmentTree(1, 1, maxn - 1);
document.write("Maximum divisors that a number " +
"has in [1, 100] are " + query(1, 1, maxn - 1, 1, 100)+"<br>");
document.write("Maximum divisors that a number " +
"has in [10, 48] are " +
query(1, 1, maxn - 1, 10, 48)+"<br>");
document.write("Maximum divisors that a number " +
"has in [1, 10] are " +
query(1, 1, maxn - 1, 1, 10)+"<br>");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Maximum divisors that a number has in [1, 100] are 12 Maximum divisors that a number has in [10, 48] are 10 Maximum divisors that a number has in [1, 10] are 4
Complejidad del tiempo:
For sieve: O(maxn * log(log(maxn)) ) For calculating divisors of each number: O(k1 + k2 + ... + kn) < O(log(maxn)) For querying each range: O(log(maxn)) Total: O((maxn + Q) * log(maxn))
Tema relacionado: Árbol de segmentos
Este artículo es una contribución de Saumye Malhotra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA