Requisito previo: encontrar el número primo máximo y mínimo
Dados cuatro números enteros A, B, C y X , la tarea es minimizar el costo de seleccionar dos números N y M de modo que el producto de N y M sea igual a X, es decir, N * METRO = X. El costo de seleccionar los números N y M se decide de la siguiente manera:
- Para el primer número N:
- El costo es A si N es un número primo.
- El costo es B si N es un número compuesto.
- El costo es C si N es 1.
- Para el segundo número M (!= 1), el costo es M.
Ejemplos:
Entrada: A = 7, B = 11, C = 2, X = 20
Salida: 11
Explicación:
Los siguientes son los valores posibles y el costo de cada par:
Sea N = 1 y M = 20, costo utilizado para seleccionar N como 1 es C = 2, Costo total = 2 + 20 = 22.
Sea N = 2 y M = 10, el costo utilizado para seleccionar N como número primo es A = 7, Costo total = 7 + 10 = 17
Sea N = 4 y M = 5, el costo utilizado para seleccionar N como número compuesto es B = 11, Costo total = 11 + 5 = 15
Sea N = 5 y M = 4, el costo utilizado para seleccionar N como número primo es A = 7, Costo total = 7 + 4 = 11
Sea N = 10 y M = 2, el costo utilizado para seleccionar N como número compuesto es B = 11, el costo total = 11 + 2 = 13
El mínimo entre todos los anteriores es 11.
Entrada:A = 1, B = 1, C = 1, X = 40
Salida: 3
Explicación:
El costo mínimo es cuando N = 20 y M = 2, Costo total = 1 + 2 = 3.
Enfoque ingenuo: encuentre todos los factores del número y verifique si el factor es primo o no , en consecuencia, encuentre el costo y seleccione el mínimo de ellos.
Enfoque eficiente: puede haber tres casos posibles para N de la siguiente manera:
- N es primo: entonces el costo del primer número es fijo. Para minimizar el costo, se elige el mayor número primo posible tal que N ≠ X .
- N es compuesto: similar al caso anterior, se debe encontrar el número compuesto máximo que divide el número, pero no el número en sí. Para hacer esto, se encuentra el número primo mínimo que divide a X y se considera como M y se calcula el costo.
- N es 1: Se puede formar cualquier número (excepto cuando X = 1) y M = X para este caso.
Por lo tanto, la idea es calcular el costo de los tres casos y encontrar el mínimo entre todos. Para hacer esto, la lista de todos los factores primos mínimos y factores primos máximos se precalcula utilizando una ligera variación de Tamiz de Eratóstenes y se almacena en una array. El costo de los tres casos se puede calcular fácilmente a partir de estas arrays.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100000;
// max_prime[i] represents maximum prime
// number that divides the number i
int max_prime[MAX];
// min_prime[i] represents minimum prime
// number that divides the number i
int min_prime[MAX];
// Function to store the minimum
// prime factor and the maximum
// prime factor in two arrays
void sieve(int n)
{
for (int i = 2; i <= n; ++i) {
// Check for prime number
// if min_prime[i] > 0,
// then it is not a prime number
if (min_prime[i] > 0) {
continue;
}
// If i is a prime number,
// then both minimum and maximum
// prime numbers that divide
// the number is the number itself
min_prime[i] = i;
max_prime[i] = i;
int j = i + i;
while (j <= n) {
if (min_prime[j] == 0) {
// If this number is being visited
// for first time then this divisor
// must be the smallest prime number
// that divides this number
min_prime[j] = i;
}
// Update prime number till the last
// prime number that divides this number
// The last prime number that
// divides this number will be maximum.
max_prime[j] = i;
j += i;
}
}
}
// Function to minimize the cost of finding
// two numbers for every number such that
// the product of those two is equal to X
int findCost(int A, int B, int C, int X)
{
// Pre-calculation
sieve(MAX);
int N, M;
// If X == 1, then there is no way to
// find N and M. Print -1
if (X == 1) {
return -1;
}
// Case 3 is always valid and cost for that
// is C + X C for choosing 1 and M = X/1
int min_cost = C + X;
// Case 1
// N is prime, first number cost is fixed
// N is max_prime number divides this number
int cost_for_prime = A;
N = max_prime[X];
// If X is prime then the maximum prime number
// is the number itself. For this case,
// M becomes 1 and this shouldn't be considered.
if (N != X) {
// Find M for this case
M = X / N;
// Add cost for the second number also
cost_for_prime += M;
// Update min_cost, if the
// cost for prime is minimum
min_cost = min(min_cost, cost_for_prime);
}
// Case 2
// If N is composite
// For this find the minimum prime number
// that divides A[i] and consider this as M
M = min_prime[X];
// Find N for that number
N = X / M;
// Check if this number is composite or not
// if N is prime then there is no way
// to find any composite number that divides X
// If N = min_prime[N] then N is prime
if (N != min_prime[N]) {
int cost_for_comp = B + M;
// Update min_cost, if the
// cost for the composite is minimum
min_cost = min(min_cost, cost_for_comp);
}
return min_cost;
}
// Driver code
int main()
{
int A = 7, B = 11, C = 2, X = 20;
cout << findCost(A, B, C, X) << " ";
return 0;
}
Java
// Java implementation of the above approach
class GFG {
static final int MAX = 1000;
// max_prime[i] represents maximum prime
// number that divides the number i
static int max_prime[] = new int[MAX];
// min_prime[i] represents minimum prime
// number that divides the number i
static int min_prime[] = new int[MAX];
// Function to store the minimum
// prime factor and the maximum
// prime factor in two arrays
static void sieve(int n)
{
for (int i = 2; i < n; ++i) {
// Check for prime number
// if min_prime[i] > 0,
// then it is not a prime number
if (min_prime[i] > 0) {
continue;
}
// If i is a prime number,
// then both minimum and maximum
// prime numbers that divide
// the number is the number itself
min_prime[i] = i;
max_prime[i] = i;
int j = i + i;
while (j < n) {
if (min_prime[j] == 0) {
// If this number is being visited
// for first time then this divisor
// must be the smallest prime number
// that divides this number
min_prime[j] = i;
}
// Update prime number till the last
// prime number that divides this number
// The last prime number that
// divides this number will be maximum.
max_prime[j] = i;
j += i;
}
}
}
// Function to minimize the cost of finding
// two numbers for every number such that
// the product of those two is equal to X
static int findCost(int A, int B, int C, int X)
{
// Pre-calculation
sieve(MAX);
int N, M;
// If X == 1, then there is no way to
// find N and M. Print -1
if (X == 1) {
return -1;
}
// Case 3 is always valid and cost for that
// is C + X C for choosing 1 and M = X/1
int min_cost = C + X;
// Case 1
// N is prime, first number cost is fixed
// N is max_prime number divides this number
int cost_for_prime = A;
N = max_prime[X];
// If X is prime then the maximum prime number
// is the number itself. For this case,
// M becomes 1 and this shouldn't be considered.
if (N != X) {
// Find M for this case
M = X / N;
// Add cost for the second number also
cost_for_prime += M;
// Update min_cost, if the
// cost for prime is minimum
min_cost = Math.min(min_cost, cost_for_prime);
}
// Case 2
// If N is composite
// For this find the minimum prime number
// that divides A[i] and consider this as M
M = min_prime[X];
// Find N for that number
N = X / M;
// Check if this number is composite or not
// if N is prime then there is no way
// to find any composite number that divides X
// If N = min_prime[N] then N is prime
if (N != min_prime[N]) {
int cost_for_comp = B + M;
// Update min_cost, if the
// cost for the composite is minimum
min_cost = Math.min(min_cost, cost_for_comp);
}
return min_cost;
}
// Driver code
public static void main (String[] args)
{
int A = 7, B = 11, C = 2, X = 20;
System.out.println(findCost(A, B, C, X));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of # the above approach MAX = 10000; # max_prime[i] represents maximum prime # number that divides the number i max_prime = [0]*MAX; # min_prime[i] represents minimum prime # number that divides the number i min_prime = [0]*MAX; # Function to store the minimum # prime factor and the maximum # prime factor in two arrays def sieve(n) : for i in range(2, n) : # Check for prime number # if min_prime[i] > 0, # then it is not a prime number if (min_prime[i] > 0) : continue; # If i is a prime number, # then both minimum and maximum # prime numbers that divide # the number is the number itself min_prime[i] = i; max_prime[i] = i; j = i + i; while (j < n) : if (min_prime[j] == 0) : # If this number is being visited # for first time then this divisor # must be the smallest prime number # that divides this number min_prime[j] = i; # Update prime number till the last # prime number that divides this number # The last prime number that # divides this number will be maximum. max_prime[j] = i; j += i; # Function to minimize the cost of finding # two numbers for every number such that # the product of those two is equal to X def findCost(A, B, C, X) : # Pre-calculation sieve(MAX); # If X == 1, then there is no way to # find N and M. Print -1 if (X == 1) : return -1; # Case 3 is always valid and cost for that # is C + X C for choosing 1 and M = X/1 min_cost = C + X; # Case 1 # N is prime, first number cost is fixed # N is max_prime number divides this number cost_for_prime = A; N = max_prime[X]; # If X is prime then the maximum prime number # is the number itself. For this case, # M becomes 1 and this shouldn't be considered. if (N != X) : # Find M for this case M = X // N; # Add cost for the second number also cost_for_prime += M; # Update min_cost, if the # cost for prime is minimum min_cost = min(min_cost, cost_for_prime); # Case 2 # If N is composite # For this find the minimum prime number # that divides A[i] and consider this as M M = min_prime[X]; # Find N for that number N = X // M; # Check if this number is composite or not # if N is prime then there is no way # to find any composite number that divides X # If N = min_prime[N] then N is prime if (N != min_prime[N]) : cost_for_comp = B + M; # Update min_cost, if the # cost for the composite is minimum min_cost = min(min_cost, cost_for_comp); return min_cost; # Driver code if __name__ == "__main__" : A = 7; B = 11; C = 2; X = 20; print(findCost(A, B, C, X)) ; # This code is contributed by AnkitRai01
C#
// C# implementation of the above approach
using System;
class GFG {
static int MAX = 1000;
// max_prime[i] represents maximum prime
// number that divides the number i
static int []max_prime = new int[MAX];
// min_prime[i] represents minimum prime
// number that divides the number i
static int []min_prime = new int[MAX];
// Function to store the minimum
// prime factor and the maximum
// prime factor in two arrays
static void sieve(int n)
{
for (int i = 2; i < n; ++i) {
// Check for prime number
// if min_prime[i] > 0,
// then it is not a prime number
if (min_prime[i] > 0) {
continue;
}
// If i is a prime number,
// then both minimum and maximum
// prime numbers that divide
// the number is the number itself
min_prime[i] = i;
max_prime[i] = i;
int j = i + i;
while (j < n) {
if (min_prime[j] == 0) {
// If this number is being visited
// for first time then this divisor
// must be the smallest prime number
// that divides this number
min_prime[j] = i;
}
// Update prime number till the last
// prime number that divides this number
// The last prime number that
// divides this number will be maximum.
max_prime[j] = i;
j += i;
}
}
}
// Function to minimize the cost of finding
// two numbers for every number such that
// the product of those two is equal to X
static int findCost(int A, int B, int C, int X)
{
// Pre-calculation
sieve(MAX);
int N, M;
// If X == 1, then there is no way to
// find N and M. Print -1
if (X == 1) {
return -1;
}
// Case 3 is always valid and cost for that
// is C + X C for choosing 1 and M = X/1
int min_cost = C + X;
// Case 1
// N is prime, first number cost is fixed
// N is max_prime number divides this number
int cost_for_prime = A;
N = max_prime[X];
// If X is prime then the maximum prime number
// is the number itself. For this case,
// M becomes 1 and this shouldn't be considered.
if (N != X) {
// Find M for this case
M = X / N;
// Add cost for the second number also
cost_for_prime += M;
// Update min_cost, if the
// cost for prime is minimum
min_cost = Math.Min(min_cost, cost_for_prime);
}
// Case 2
// If N is composite
// For this find the minimum prime number
// that divides A[i] and consider this as M
M = min_prime[X];
// Find N for that number
N = X / M;
// Check if this number is composite or not
// if N is prime then there is no way
// to find any composite number that divides X
// If N = min_prime[N] then N is prime
if (N != min_prime[N]) {
int cost_for_comp = B + M;
// Update min_cost, if the
// cost for the composite is minimum
min_cost = Math.Min(min_cost, cost_for_comp);
}
return min_cost;
}
// Driver code
public static void Main (string[] args)
{
int A = 7, B = 11, C = 2, X = 20;
Console.WriteLine(findCost(A, B, C, X));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the above approach
let MAX = 1000;
// max_prime[i] represents maximum prime
// number that divides the number i
let max_prime = Array.from({length: MAX}, (_, i) => 0);
// min_prime[i] represents minimum prime
// number that divides the number i
let min_prime = Array.from({length: MAX}, (_, i) => 0);
// Function to store the minimum
// prime factor and the maximum
// prime factor in two arrays
function sieve(n)
{
for (let i = 2; i < n; ++i) {
// Check for prime number
// if min_prime[i] > 0,
// then it is not a prime number
if (min_prime[i] > 0) {
continue;
}
// If i is a prime number,
// then both minimum and maximum
// prime numbers that divide
// the number is the number itself
min_prime[i] = i;
max_prime[i] = i;
let j = i + i;
while (j < n) {
if (min_prime[j] == 0) {
// If this number is being visited
// for first time then this divisor
// must be the smallest prime number
// that divides this number
min_prime[j] = i;
}
// Update prime number till the last
// prime number that divides this number
// The last prime number that
// divides this number will be maximum.
max_prime[j] = i;
j += i;
}
}
}
// Function to minimize the cost of finding
// two numbers for every number such that
// the product of those two is equal to X
function findCost(A, B, C, X)
{
// Pre-calculation
sieve(MAX);
let N, M;
// If X == 1, then there is no way to
// find N and M. Print -1
if (X == 1) {
return -1;
}
// Case 3 is always valid and cost for that
// is C + X C for choosing 1 and M = X/1
let min_cost = C + X;
// Case 1
// N is prime, first number cost is fixed
// N is max_prime number divides this number
let cost_for_prime = A;
N = max_prime[X];
// If X is prime then the maximum prime number
// is the number itself. For this case,
// M becomes 1 and this shouldn't be considered.
if (N != X) {
// Find M for this case
M = X / N;
// Add cost for the second number also
cost_for_prime += M;
// Update min_cost, if the
// cost for prime is minimum
min_cost = Math.min(min_cost, cost_for_prime);
}
// Case 2
// If N is composite
// For this find the minimum prime number
// that divides A[i] and consider this as M
M = min_prime[X];
// Find N for that number
N = X / M;
// Check if this number is composite or not
// if N is prime then there is no way
// to find any composite number that divides X
// If N = min_prime[N] then N is prime
if (N != min_prime[N]) {
let cost_for_comp = B + M;
// Update min_cost, if the
// cost for the composite is minimum
min_cost = Math.min(min_cost, cost_for_comp);
}
return min_cost;
}
// Driver Code
let A = 7, B = 11, C = 2, X = 20;
document.write(findCost(A, B, C, X));
</script>
Producción:
11
Complejidad de tiempo: O(MAX) 2
Espacio Auxiliar: O(MAX)
Publicación traducida automáticamente
Artículo escrito por shivamsinghal1012 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA