Dado un número X , la tarea es encontrar el número mínimo N tal que la suma de la cuenta de todos los factores de 1 a N sea mayor que igual a X.
Ejemplos:
Entrada: X = 10
Salida: 5
Explicación:
Factores totales de 1 = 1 (1)
Factores totales de 2 = 2 (1, 2)
Factores totales de 3 = 2 (1, 3)
Factores totales de 4 = 3 (1, 2, 4)
Factores totales de 5 = 2 (1, 5)
Conteo total = 1 + 2 + 2 + 3 + 2 = 10 que es mayor o igual a X, es decir, 10
Entrada: X = 19
Salida: 8
Explicación :
Factores totales de 1 = 1 (1)
Factores totales de 2 = 2 (1, 2)
Factores totales de 3 = 2 (1, 3)
Factores totales de 4 = 3 (1, 2, 4)
Factores totales de 5 = 2 (1, 5)
Factores totales de 6 = 2 (1, 2, 3, 6)
Factores totales de 7 = 2 (1, 7)
Factores totales de 8 = 2 (1, 2, 4, 8)
Recuento total = 1 + 2 + 2 + 3 + 2 + 4 + 2 + 4 = 20 que es mayor o igual a X, es decir, 19
Enfoque ingenuo: el enfoque ingenuo consiste en ejecutar un ciclo que comienza desde 1 hasta que el recuento total del factor sea mayor que igual a X .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000050
#define lli long int
// Function to count total factors of N
lli CountFactors(lli N)
{
lli cnt = 0;
for (lli i = 1;
i * i <= N; i++) {
if (N % i == 0)
cnt += ((N / i == i) ? 1 : 2);
}
// Return the count
return cnt;
}
// Function to search lowest N
// such that the given condition
// is satisfied
lli minN(lli X)
{
lli i = 1;
lli total = 0;
while (1) {
// Add the count of total factor
// of i to variable total
total = total + CountFactors(i);
// If total count is greater than
// equal to N, then return i
if (total >= X)
return i;
i++;
}
}
// Driver Code
int main()
{
// Given sum
lli X = 10;
// Function Call
cout << minN(X) << endl;
return 0;
}
Java
// Java program for the above approach
class GFG{
static final int MAX = 1000050;
// Function to count total factors of N
static int CountFactors(int N)
{
int cnt = 0;
for(int i = 1; i * i <= N; i++)
{
if (N % i == 0)
cnt += ((N / i == i) ? 1 : 2);
}
// Return the count
return cnt;
}
// Function to search lowest N
// such that the given condition
// is satisfied
static int minN(int X)
{
int i = 1;
int total = 0;
while (true)
{
// Add the count of total factor
// of i to variable total
total = total + CountFactors(i);
// If total count is greater than
// equal to N, then return i
if (total >= X)
return i;
i++;
}
}
// Driver Code
public static void main(String[] args)
{
// Given sum
int X = 10;
// Function Call
System.out.print(minN(X) + "\n");
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program for # the above approach MAX = 1000050 # Function to count # total factors of N def CountFactors(N): cnt = 0 i = 1 while i * i <= N: if (N % i == 0): if (N // i == i): cnt += 1 else: cnt += 2 i += 1 # Return the count return cnt # Function to search lowest N # such that the given condition # is satisfied def minN(X): i = 1 total = 0 while (1): # Add the count of total factor # of i to variable total total = total + CountFactors(i) # If total count is greater than # equal to N, then return i if (total >= X): return i i += 1 # Driver Code if __name__ == "__main__": # Given sum X = 10 # Function Call print( minN(X)) # This code is contributed by Chitranayal
C#
// C# program for the above approach
using System;
class GFG{
//static readonly int MAX = 1000050;
// Function to count total factors of N
static int CountFactors(int N)
{
int cnt = 0;
for(int i = 1; i * i <= N; i++)
{
if (N % i == 0)
cnt += ((N / i == i) ? 1 : 2);
}
// Return the count
return cnt;
}
// Function to search lowest N
// such that the given condition
// is satisfied
static int minN(int X)
{
int i = 1;
int total = 0;
while (true)
{
// Add the count of total factor
// of i to variable total
total = total + CountFactors(i);
// If total count is greater than
// equal to N, then return i
if (total >= X)
return i;
i++;
}
}
// Driver Code
public static void Main(String[] args)
{
// Given sum
int X = 10;
// Function Call
Console.Write(minN(X) + "\n");
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// javascript program for the above approachstatic final var MAX = 1000050;
// Function to count total factors of N
function CountFactors(N)
{
var cnt = 0;
for(i = 1; i * i <= N; i++)
{
if (N % i == 0)
cnt += ((N / i == i) ? 1 : 2);
}
// Return the count
return cnt;
}
// Function to search lowest N
// such that the given condition
// is satisfied
function minN(X)
{
var i = 1;
var total = 0;
while (true)
{
// Add the count of total factor
// of i to variable total
total = total + CountFactors(i);
// If total count is greater than
// equal to N, then return i
if (total >= X)
return i;
i++;
}
}
// Driver Code
//Given sum
var X = 10;
// Function Call
document.write(minN(X) + "\n");
// This code is contributed by 29AjayKumar
</script>
Producción:
5
Complejidad de tiempo: O(N*sqrt(N))
Espacio auxiliar: O(1)
Enfoque eficiente: El enfoque anterior se puede optimizar haciendo algunos cálculos previos. A continuación se muestran los pasos:
- Calcule y almacene el factor primo más pequeño de cada número (SPF) usando el enfoque que se describe en este artículo.
- Encuentre el conteo de factores de N de manera eficiente, utilizando la criba de Eratóstenes y el factor primo más pequeño calculado anteriormente.
- Cree una array de suma de prefijos para almacenar la suma del recuento de factores de 1 a MAX .
- Para encontrar el N más bajo que satisfaga la condición anterior, en lugar de una búsqueda lineal en la array de prefijos, realice una búsqueda binaria en la array de suma de prefijos (ya que la array de suma de prefijos estará en orden creciente), de modo que la complejidad del tiempo sea óptima para múltiples consultas también.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000050
#define lli long int
// Array to store smallest
// prime factors of each no.
lli spf[MAX + 1];
// Function to calculate smallest
// prime factor of N.
void calculate_SPF()
{
for (lli i = 0; i <= MAX; i++)
spf[i] = i;
for (lli i = 4; i <= MAX; i += 2)
spf[i] = 2;
for (lli i = 3;
i * i <= MAX; i++) {
if (spf[i] == i) {
for (int j = i * i;
j <= MAX; j += i)
// marking spf[j] if
// it is not previously
// marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Array to store the count of
// factor for N
lli tfactor[MAX + 1];
// Prefix array which contains
// the count of factors from 1 to N
lli pre[MAX + 1];
// Function to count total factors
// from 1 to N
void CountTotalfactors()
{
tfactor[1] = pre[1] = 1;
for (lli i = 2; i <= MAX; i++) {
lli mspf = spf[i];
lli prim = mspf;
lli temp = i;
lli cnt = 0;
while (temp % mspf == 0) {
temp /= mspf;
cnt += 1;
prim = prim * mspf;
}
// Store total factors of i
tfactor[i] = (cnt + 1)
* tfactor[temp];
// Stores total factors
// from 1 to i
pre[i] = pre[i - 1]
+ tfactor[i];
}
}
// Function to search lowest X
// such that the given condition
// is satisfied
lli BinarySearch(lli X)
{
lli start = 1;
lli end = MAX - 1;
while (start < end) {
// Find mid
lli mid = (start + end) / 2;
if (pre[mid] == X)
return mid;
// Search in the right half
else if (pre[mid] < X)
start = mid + 1;
// Search in the left half
else
end = mid;
}
// Return the position after
// Binary Search
return start;
}
// Function to find the required sum
void findSumOfCount(int X)
{
// Precompute smallest prime
// factor of each value
calculate_SPF();
// Calculate count of total
// factors from 1 to N
CountTotalfactors();
// Binary search to find minimum N
cout << BinarySearch(X)
<< endl;
}
// Driver Code
int main()
{
// Given Sum
int X = 10;
// Function Call
findSumOfCount(X);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static final int MAX = 1000050;
// Array to store smallest
// prime factors of each no.
static int []spf = new int[MAX + 1];
// Function to calculate smallest
// prime factor of N.
static void calculate_SPF()
{
for(int i = 0; i <= MAX; i++)
spf[i] = i;
for(int i = 4; i <= MAX; i += 2)
spf[i] = 2;
for(int i = 3; i * i <= MAX; i++)
{
if (spf[i] == i)
{
for(int j = i * i;
j <= MAX; j += i)
// marking spf[j] if
// it is not previously
// marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Array to store the count of
// factor for N
static int []tfactor = new int[MAX + 1];
// Prefix array which contains
// the count of factors from 1 to N
static int []pre = new int[MAX + 1];
// Function to count total factors
// from 1 to N
static void CountTotalfactors()
{
tfactor[1] = pre[1] = 1;
for(int i = 2; i <= MAX; i++)
{
int mspf = spf[i];
int prim = mspf;
int temp = i;
int cnt = 0;
while (temp % mspf == 0)
{
temp /= mspf;
cnt += 1;
prim = prim * mspf;
}
// Store total factors of i
tfactor[i] = (cnt + 1) * tfactor[temp];
// Stores total factors
// from 1 to i
pre[i] = pre[i - 1] + tfactor[i];
}
}
// Function to search lowest X
// such that the given condition
// is satisfied
static int BinarySearch(int X)
{
int start = 1;
int end = MAX - 1;
while (start < end)
{
// Find mid
int mid = (start + end) / 2;
if (pre[mid] == X)
return mid;
// Search in the right half
else if (pre[mid] < X)
start = mid + 1;
// Search in the left half
else
end = mid;
}
// Return the position after
// Binary Search
return start;
}
// Function to find the required sum
static void findSumOfCount(int X)
{
// Precompute smallest prime
// factor of each value
calculate_SPF();
// Calculate count of total
// factors from 1 to N
CountTotalfactors();
// Binary search to find minimum N
System.out.print(BinarySearch(X) + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Given Sum
int X = 10;
// Function Call
findSumOfCount(X);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program for the # above approach MAX = 1000050 # Array to store smallest # prime factors of each no. spf = [0 for i in range(MAX + 1)] # Function to calculate smallest # prime factor of N. def calculate_SPF(): for i in range(MAX + 1): spf[i] = i; for i in range(4, MAX + 1, 2): spf[i] = 2; i = 3 while(i * i <= MAX): if (spf[i] == i) j = i * i while(j <= MAX): # Marking spf[j] if # it is not previously # marked if (spf[j] == j): spf[j] = i; j += i i += 1 # Array to store the # count of factor for N tfactor = [0 for i in range(MAX + 1)] # Prefix array which contains # the count of factors from 1 to N pre = [0 for i in range(MAX + 1)] # Function to count # total factors from 1 to N def CountTotalfactors(): tfactor[1] = pre[1] = 1; for i in range(2, MAX + 1): mspf = spf[i]; prim = mspf; temp = i; cnt = 0; while (temp % mspf == 0): temp //= mspf; cnt += 1; prim = prim * mspf; # Store total factors of i tfactor[i] = (cnt + 1) * tfactor[temp]; # Stores total factors # from 1 to i pre[i] = pre[i - 1] + tfactor[i]; # Function to search lowest X # such that the given condition # is satisfied def BinarySearch(X): start = 1; end = MAX - 1; while (start < end): # Find mid mid = (start + end) // 2; if (pre[mid] == X): return mid; # Search in the right half elif (pre[mid] < X): start = mid + 1; # Search in the left half else: end = mid; # Return the position after # Binary Search return start; # Function to find the # required sum def findSumOfCount(X): # Precompute smallest prime # factor of each value calculate_SPF(); # Calculate count of total # factors from 1 to N CountTotalfactors(); # Binary search to find # minimum N print(BinarySearch(X)) # Driver code if __name__ == "__main__": # Given Sum X = 10; # Function Call findSumOfCount(X); # This code is contributed by rutvik_56
C#
// C# program for the above approach
using System;
class GFG{
const int MAX = 1000050;
// Array to store smallest
// prime factors of each no.
static int []spf = new int[MAX + 1];
// Function to calculate smallest
// prime factor of N.
static void calculate_SPF()
{
for(int i = 0; i <= MAX; i++)
spf[i] = i;
for(int i = 4; i <= MAX; i += 2)
spf[i] = 2;
for(int i = 3; i * i <= MAX; i++)
{
if (spf[i] == i)
{
for(int j = i * i;
j <= MAX; j += i)
// marking spf[j] if
// it is not previously
// marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Array to store the count of
// factor for N
static int []tfactor = new int[MAX + 1];
// Prefix array which contains
// the count of factors from 1 to N
static int []pre = new int[MAX + 1];
// Function to count total factors
// from 1 to N
static void CountTotalfactors()
{
tfactor[1] = pre[1] = 1;
for(int i = 2; i <= MAX; i++)
{
int mspf = spf[i];
int prim = mspf;
int temp = i;
int cnt = 0;
while (temp % mspf == 0)
{
temp /= mspf;
cnt += 1;
prim = prim * mspf;
}
// Store total factors of i
tfactor[i] = (cnt + 1) * tfactor[temp];
// Stores total factors
// from 1 to i
pre[i] = pre[i - 1] + tfactor[i];
}
}
// Function to search lowest X
// such that the given condition
// is satisfied
static int BinarySearch(int X)
{
int start = 1;
int end = MAX - 1;
while (start < end)
{
// Find mid
int mid = (start + end) / 2;
if (pre[mid] == X)
return mid;
// Search in the right half
else if (pre[mid] < X)
start = mid + 1;
// Search in the left half
else
end = mid;
}
// Return the position after
// Binary Search
return start;
}
// Function to find the required sum
static void findSumOfCount(int X)
{
// Precompute smallest prime
// factor of each value
calculate_SPF();
// Calculate count of total
// factors from 1 to N
CountTotalfactors();
// Binary search to find minimum N
Console.Write(BinarySearch(X) + "\n");
}
// Driver Code
public static void Main()
{
// Given Sum
int X = 10;
// Function Call
findSumOfCount(X);
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// JavaScript program for the above approach
var MAX = 1000050;
// Array to store smallest
// prime factors of each no.
var spf = Array(MAX+1);
// Function to calculate smallest
// prime factor of N.
function calculate_SPF()
{
for (var i = 0; i <= MAX; i++)
spf[i] = i;
for (var i = 4; i <= MAX; i += 2)
spf[i] = 2;
for (var i = 3;
i * i <= MAX; i++) {
if (spf[i] == i) {
for (var j = i * i;
j <= MAX; j += i)
// marking spf[j] if
// it is not previously
// marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Array to store the count of
// factor for N
var tfactor = Array(MAX+1);
// Prefix array which contains
// the count of factors from 1 to N
var pre = Array(MAX+1);
// Function to count total factors
// from 1 to N
function CountTotalfactors()
{
tfactor[1] = pre[1] = 1;
for (var i = 2; i <= MAX; i++) {
var mspf = spf[i];
var prim = mspf;
var temp = i;
var cnt = 0;
while (temp % mspf == 0) {
temp = parseInt(temp/mspf);
cnt += 1;
prim = prim * mspf;
}
// Store total factors of i
tfactor[i] = (cnt + 1)
* tfactor[temp];
// Stores total factors
// from 1 to i
pre[i] = pre[i - 1]
+ tfactor[i];
}
}
// Function to search lowest X
// such that the given condition
// is satisfied
function BinarySearch(X)
{
var start = 1;
var end = MAX - 1;
while (start < end) {
// Find mid
var mid = parseInt((start + end) / 2);
if (pre[mid] == X)
return mid;
// Search in the right half
else if (pre[mid] < X)
start = mid + 1;
// Search in the left half
else
end = mid;
}
// Return the position after
// Binary Search
return start;
}
// Function to find the required sum
function findSumOfCount( X)
{
// Precompute smallest prime
// factor of each value
calculate_SPF();
// Calculate count of total
// factors from 1 to N
CountTotalfactors();
// Binary search to find minimum N
document.write( BinarySearch(X) + "<br>");
}
// Driver Code
// Given Sum
var X = 10;
// Function Call
findSumOfCount(X);
</script>
Producción:
5
Complejidad de tiempo: O(MAX*log(MAX))
Espacio auxiliar: O(MAX)
Nota: si hay consultas Q , entonces la complejidad de tiempo para encontrar N para todas las consultas Q será O(Q*log(MAX)) .
Publicación traducida automáticamente
Artículo escrito por Chandan_Agrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA