Dados dos números X e Y. La tarea es encontrar el número de elementos en el rango [X,Y] ambos inclusive, que tienen el máximo número de divisores.
Ejemplos :
Entrada : X = 2, Y = 9
Salida : 2
6, 8 son números con el número máximo de divisores.Entrada : X = 1, Y = 10
Salida : 3
6, 8, 10 son números con el máximo número de divisores.
Método 1:
- Recorre todos los elementos de X a Y uno por uno.
- Encuentra el número de divisores de cada elemento.
- Almacene la cantidad de divisores en una array y actualice la cantidad máxima de divisores (maxDivisors).
- Recorre la array que contiene divisores y cuenta el número de elementos igual a maxDivisors.
- Devuelve la cuenta.
A continuación se muestra la implementación del método anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the divisors
int countDivisors(int n)
{
int count = 0;
// Note that this loop runs till square root
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
// If divisors are equal, print only one
if (n / i == i)
count++;
else // Otherwise print both
count += 2;
}
}
return count;
}
// Function to count the number with
// maximum divisors
int MaximumDivisors(int X, int Y)
{
int maxDivisors = INT_MIN, result = 0;
// to store number of divisors
int arr[Y - X + 1];
// Traverse from X to Y
for (int i = X; i <= Y; i++) {
// Count the number of divisors of i
int Div = countDivisors(i);
// Store the value of div in an array
arr[i - X] = Div;
// Update the value of maxDivisors
maxDivisors = max(Div, maxDivisors);
}
// Traverse the array
for (int i = 0; i < (Y - X + 1); i++)
// Count the value equals to maxDivisors
if (arr[i] == maxDivisors)
result++;
return result;
}
// Driver Code
int main()
{
int X = 1, Y = 10;
// function call
cout << MaximumDivisors(X, Y) << endl;
return 0;
}
C
// C implementation of above approach
#include <stdio.h>
#include <math.h>
#include <limits.h>
int max(int a,int b)
{
int max = a;
if(max < b)
max = b;
return max;
}
// Function to count the divisors
int countDivisors(int n)
{
int count = 0;
// Note that this loop runs till square root
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
// If divisors are equal, print only one
if (n / i == i)
count++;
else // Otherwise print both
count += 2;
}
}
return count;
}
// Function to count the number with
// maximum divisors
int MaximumDivisors(int X, int Y)
{
int maxDivisors = INT_MIN, result = 0;
// to store number of divisors
int arr[Y - X + 1];
// Traverse from X to Y
for (int i = X; i <= Y; i++) {
// Count the number of divisors of i
int Div = countDivisors(i);
// Store the value of div in an array
arr[i - X] = Div;
// Update the value of maxDivisors
maxDivisors = max(Div, maxDivisors);
}
// Traverse the array
for (int i = 0; i < (Y - X + 1); i++)
// Count the value equals to maxDivisors
if (arr[i] == maxDivisors)
result++;
return result;
}
// Driver Code
int main()
{
int X = 1, Y = 10;
// function call
printf("%d\n",MaximumDivisors(X, Y));
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java implementation of above approach
class GFG
{
// Function to count the divisors
static int countDivisors(int n)
{
int count = 0;
// Note that this loop
// runs till square root
for (int i = 1; i <= Math.sqrt(n); i++)
{
if (n % i == 0)
{
// If divisors are equal,
// print only one
if (n / i == i)
count++;
else // Otherwise print both
count += 2;
}
}
return count;
}
// Function to count the number
// with maximum divisors
static int MaximumDivisors(int X, int Y)
{
int maxDivisors = 0, result = 0;
// to store number of divisors
int[] arr = new int[Y - X + 1];
// Traverse from X to Y
for (int i = X; i <= Y; i++)
{
// Count the number of divisors of i
int Div = countDivisors(i);
// Store the value of div in an array
arr[i - X] = Div;
// Update the value of maxDivisors
maxDivisors = Math.max(Div, maxDivisors);
}
// Traverse the array
for (int i = 0; i < (Y - X + 1); i++)
// Count the value equals
// to maxDivisors
if (arr[i] == maxDivisors)
result++;
return result;
}
// Driver Code
public static void main(String[] args)
{
int X = 1, Y = 10;
// function call
System.out.println(MaximumDivisors(X, Y));
}
}
// This code is contributed
// by ChitraNayal
Python3
# from math module import everything from math import * # Python 3 implementation of above approach # Function to count the divisors def countDivisors(n) : count = 0 # Note that this loop runs till square root for i in range(1,int(sqrt(n)+1)) : if n % i == 0 : # If divisors are equal, print only one if n / i == i : count += 1 # Otherwise print both else : count += 2 return count # Function to count the number with # maximum divisors def MaximumDivisors(X,Y) : result = 0 maxDivisors = 0 # create list to store number of divisors arr = [] # initialize with 0 upto length Y-X+1 for i in range(Y - X + 1) : arr.append(0) # Traverse from X to Y for i in range(X,Y+1) : # Count the number of divisors of i Div = countDivisors(i) # Store the value of div in an array arr[i - X] = Div # Update the value of maxDivisors maxDivisors = max(Div,maxDivisors) # Traverse the array for i in range (Y - X + 1) : # Count the value equals to maxDivisors if arr[i] == maxDivisors : result += 1 return result # Driver code if __name__ == "__main__" : X, Y = 1, 10 # function call print(MaximumDivisors(X,Y))
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to count the divisors
static int countDivisors(int n)
{
int count = 0;
// Note that this loop
// runs till square root
for (int i = 1; i <= Math.Sqrt(n); i++)
{
if (n % i == 0)
{
// If divisors are equal,
// print only one
if (n / i == i)
count++;
else // Otherwise print both
count += 2;
}
}
return count;
}
// Function to count the number
// with maximum divisors
static int MaximumDivisors(int X, int Y)
{
int maxDivisors = 0, result = 0;
// to store number of divisors
int[] arr = new int[Y - X + 1];
// Traverse from X to Y
for (int i = X; i <= Y; i++)
{
// Count the number of divisors of i
int Div = countDivisors(i);
// Store the value of div in an array
arr[i - X] = Div;
// Update the value of maxDivisors
maxDivisors = Math.Max(Div, maxDivisors);
}
// Traverse the array
for (int i = 0; i < (Y - X + 1); i++)
// Count the value equals
// to maxDivisors
if (arr[i] == maxDivisors)
result++;
return result;
}
// Driver Code
public static void Main()
{
int X = 1, Y = 10;
// function call
Console.Write(MaximumDivisors(X, Y));
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP implementation of above approach
// Function to count the divisors
function countDivisors($n)
{
$count = 0;
// Note that this loop
// runs till square root
for ($i = 1; $i <= sqrt($n); $i++)
{
if ($n % $i == 0)
{
// If divisors are equal,
// print only one
if ($n / $i == $i)
$count++;
else // Otherwise print both
$count += 2;
}
}
return $count;
}
// Function to count the number
// with maximum divisors
function MaximumDivisors($X, $Y)
{
$maxDivisors = PHP_INT_MIN;
$result = 0;
// to store number of divisors
$arr = array_fill(0, ($Y - $X + 1), NULL);
// Traverse from X to Y
for ($i = $X; $i <= $Y; $i++)
{
// Count the number of divisors of i
$Div = countDivisors($i);
// Store the value of div in an array
$arr[$i - $X] = $Div;
// Update the value of maxDivisors
$maxDivisors = max($Div, $maxDivisors);
}
// Traverse the array
for ($i = 0; $i < ($Y - $X + 1); $i++)
// Count the value equals to maxDivisors
if ($arr[$i] == $maxDivisors)
$result++;
return $result;
}
// Driver Code
$X = 1;
$Y = 10;
// function call
echo MaximumDivisors($X, $Y)." ";
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript implementation of above approach
// Function to count the divisors
function countDivisors(n)
{
let count = 0;
// Note that this loop
// runs till square root
for(let i = 1; i <= Math.sqrt(n); i++)
{
if (n % i == 0)
{
// If divisors are equal,
// print only one
if (Math.floor(n / i) == i)
count++;
else
// Otherwise print both
count += 2;
}
}
return count;
}
// Function to count the number
// with maximum divisors
function MaximumDivisors(X, Y)
{
let maxDivisors = 0, result = 0;
// To store number of divisors
let arr = new Array(Y - X + 1);
// Traverse from X to Y
for(let i = X; i <= Y; i++)
{
// Count the number of divisors of i
let Div = countDivisors(i);
// Store the value of div in an array
arr[i - X] = Div;
// Update the value of maxDivisors
maxDivisors = Math.max(Div, maxDivisors);
}
// Traverse the array
for(let i = 0; i < (Y - X + 1); i++)
// Count the value equals
// to maxDivisors
if (arr[i] == maxDivisors)
result++;
return result;
}
// Driver Code
let X = 1, Y = 10;
// Function call
document.write(MaximumDivisors(X, Y));
// This code is contributed by rag2127
</script>
Producción:
3
Método 2:
- Cree una array de tamaño Y-X+1 para almacenar el número de divisores de X en arr[0], X+1 en arr[1]… hasta Y.
- Para obtener el número de divisores de todos los números de X a Y, ejecute dos bucles (anidados).
- Ejecute un ciclo externo de 1 a sqrt(Y) .
- Ejecute un ciclo interno desde first_divisible hasta Y .
- First_divisible es el número que es el primer número divisible por I (bucle externo) y mayor o igual a X.
Aquí, first_divisible se calcula utilizando el método Buscar el número más cercano a n y divisible por m . Luego encuentra los divisores del número .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the elements
// with maximum number of divisors
int MaximumDivisors(int X, int Y)
{
// to store number of divisors
int arr[Y - X + 1];
// initialise with zero
memset(arr, 0, sizeof(arr));
// to store the maximum number of divisors
int mx = INT_MIN;
// to store required answer
int cnt = 0;
for (int i = 1; i * i <= Y; i++) {
int sq = i * i;
int first_divisible;
// Find the first divisible number
if ((X / i) * i >= X)
first_divisible = (X / i) * i;
else
first_divisible = (X / i + 1) * i;
// Count number of divisors
for (int j = first_divisible; j <= Y; j += i) {
if (j < sq)
continue;
else if (j == sq)
arr[j - X]++;
else
arr[j - X] += 2;
}
}
// Find number of elements with
// maximum number of divisors
for (int i = X; i <= Y; i++) {
if (arr[i - X] > mx) {
cnt = 1;
mx = arr[i - X];
}
else if (arr[i - X] == mx)
cnt++;
}
return cnt;
}
// Driver code
int main()
{
int X = 1, Y = 10;
cout << MaximumDivisors(X, Y) << endl;
return 0;
}
C
// C implementation of above approach
#include <stdio.h>
#include <limits.h>
#include <string.h>
// Function to count the elements
// with maximum number of divisors
int MaximumDivisors(int X, int Y)
{
// to store number of divisors
int arr[Y - X + 1];
// initialise with zero
memset(arr, 0, sizeof(arr));
// to store the maximum number of divisors
int mx = INT_MIN;
// to store required answer
int cnt = 0;
for (int i = 1; i * i <= Y; i++) {
int sq = i * i;
int first_divisible;
// Find the first divisible number
if ((X / i) * i >= X)
first_divisible = (X / i) * i;
else
first_divisible = (X / i + 1) * i;
// Count number of divisors
for (int j = first_divisible; j <= Y; j += i) {
if (j < sq)
continue;
else if (j == sq)
arr[j - X]++;
else
arr[j - X] += 2;
}
}
// Find number of elements with
// maximum number of divisors
for (int i = X; i <= Y; i++) {
if (arr[i - X] > mx) {
cnt = 1;
mx = arr[i - X];
}
else if (arr[i - X] == mx)
cnt++;
}
return cnt;
}
// Driver code
int main()
{
int X = 1, Y = 10;
printf("%d\n",MaximumDivisors(X, Y));
return 0;
}
// This code is contributed by kothavvsaakash.
Java
// Java implementation of above approach
class GFG
{
// Function to count the elements
// with maximum number of divisors
static int MaximumDivisors(int X, int Y)
{
// to store number of divisors
int[] arr = new int[Y - X + 1];
// initialise with zero
for(int i = 0; i < arr.length; i++)
arr[i] = 0;
// to store the maximum
// number of divisors
int mx = 0;
// to store required answer
int cnt = 0;
for (int i = 1; i * i <= Y; i++)
{
int sq = i * i;
int first_divisible;
// Find the first divisible number
if ((X / i) * i >= X)
first_divisible = (X / i) * i;
else
first_divisible = (X / i + 1) * i;
// Count number of divisors
for (int j = first_divisible;
j <= Y; j += i)
{
if (j < sq)
continue;
else if (j == sq)
arr[j - X]++;
else
arr[j - X] += 2;
}
}
// Find number of elements with
// maximum number of divisors
for (int i = X; i <= Y; i++)
{
if (arr[i - X] > mx)
{
cnt = 1;
mx = arr[i - X];
}
else if (arr[i - X] == mx)
cnt++;
}
return cnt;
}
// Driver code
public static void main(String[] args)
{
int X = 1, Y = 10;
System.out.println(MaximumDivisors(X, Y));
}
}
// This code is contributed
// by ChitraNayal
Python3
# Python 3 implementation of above approach # Function to count the elements # with maximum number of divisors def MaximumDivisors(X, Y): # to store number of divisors # initialise with zero arr = [0] * (Y - X + 1) # to store the maximum # number of divisors mx = 0 # to store required answer cnt = 0 i = 1 while i * i <= Y : sq = i * i # Find the first divisible number if ((X // i) * i >= X) : first_divisible = (X // i) * i else: first_divisible = (X // i + 1) * i # Count number of divisors for j in range(first_divisible, Y + 1, i): if j < sq : continue elif j == sq : arr[j - X] += 1 else: arr[j - X] += 2 i += 1 # Find number of elements with # maximum number of divisors for i in range(X, Y + 1): if arr[i - X] > mx : cnt = 1 mx = arr[i - X] elif arr[i - X] == mx : cnt += 1 return cnt # Driver code if __name__ == "__main__": X = 1 Y = 10 print(MaximumDivisors(X, Y)) # This code is contributed # by ChitraNayal
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to count the elements
// with maximum number of divisors
static int MaximumDivisors(int X, int Y)
{
// to store number of divisors
int[] arr = new int[Y - X + 1];
// initialise with zero
for(int i = 0; i < arr.Length; i++)
arr[i] = 0;
// to store the maximum
// number of divisors
int mx = 0;
// to store required answer
int cnt = 0;
for (int i = 1; i * i <= Y; i++)
{
int sq = i * i;
int first_divisible;
// Find the first divisible number
if ((X / i) * i >= X)
first_divisible = (X / i) * i;
else
first_divisible = (X / i + 1) * i;
// Count number of divisors
for (int j = first_divisible;
j <= Y; j += i)
{
if (j < sq)
continue;
else if (j == sq)
arr[j - X]++;
else
arr[j - X] += 2;
}
}
// Find number of elements with
// maximum number of divisors
for (int i = X; i <= Y; i++)
{
if (arr[i - X] > mx)
{
cnt = 1;
mx = arr[i - X];
}
else if (arr[i - X] == mx)
cnt++;
}
return cnt;
}
// Driver code
public static void Main()
{
int X = 1, Y = 10;
Console.Write(MaximumDivisors(X, Y));
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP implementation of above approach
// Function to count the elements
// with maximum number of divisors
function MaximumDivisors($X, $Y)
{
// to store number of divisors
// initialise with zero
$arr = array_fill(0,($Y - $X + 1), NULL);
// to store the maximum
// number of divisors
$mx = PHP_INT_MIN;
// to store required answer
$cnt = 0;
for ($i = 1; $i * $i <= $Y; $i++)
{
$sq = $i * $i;
// Find the first divisible number
if (($X / $i) * $i >= $X)
$first_divisible = ($X / $i) * $i;
else
$first_divisible = ($X / $i + 1) * $i;
// Count number of divisors
for ($j = $first_divisible;
$j < $Y; $j += $i)
{
if ($j < $sq)
continue;
else if ($j == $sq)
$arr[$j - $X]++;
else
$arr[$j - $X] += 2;
}
}
// Find number of elements with
// maximum number of divisors
for ($i = $X; $i <= $Y; $i++)
{
if ($arr[$i - $X] > $mx)
{
$cnt = 1;
$mx = $arr[$i - $X];
}
else if ($arr[$i - $X] == $mx)
$cnt++;
}
return $cnt;
}
// Driver code
$X = 1;
$Y = 10;
echo MaximumDivisors($X, $Y)."\n";
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript implementation of above approach
// Function to count the elements
// with maximum number of divisors
function MaximumDivisors(X, Y)
{
// To store number of divisors
let arr = new Array(Y - X + 1);
// Initialise with zero
for(let i = 0; i < arr.length; i++)
arr[i] = 0;
// To store the maximum
// number of divisors
let mx = 0;
// To store required answer
let cnt = 0;
for(let i = 1; i * i <= Y; i++)
{
let sq = i * i;
let first_divisible;
// Find the first divisible number
if (Math.floor(X / i) * i >= X)
first_divisible = Math.floor(X / i) * i;
else
first_divisible = (Math.floor(X / i) +
1) * i;
// Count number of divisors
for(let j = first_divisible;
j <= Y; j += i)
{
if (j < sq)
continue;
else if (j == sq)
arr[j - X]++;
else
arr[j - X] += 2;
}
}
// Find number of elements with
// maximum number of divisors
for(let i = X; i <= Y; i++)
{
if (arr[i - X] > mx)
{
cnt = 1;
mx = arr[i - X];
}
else if (arr[i - X] == mx)
cnt++;
}
return cnt;
}
// Driver code
let X = 1, Y = 10;
document.write(MaximumDivisors(X, Y));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
3
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA