Dados dos enteros positivos P y Q , la tarea es el mayor divisor de P que no es divisible por Q.
Ejemplos:
Entrada: P = 10, Q = 4
Salida: 10
Explicación: 10 es el número más grande que divide a 10 pero no es divisible por 4.Entrada: P = 12, Q = 6
Salida: 4
Explicación: 4 es el número más grande que divide a 12 pero no es divisible por 6.
Enfoque: El enfoque más simple es encontrar todos los divisores de P y obtener el mayor de estos divisores, que no es divisible por Q.
Complejidad temporal: O(√P)
Espacio auxiliar: O(1)
Enfoque alternativo: siga los pasos a continuación para resolver el problema:
- Almacene el conteo de frecuencias de factores primos de Q en divisores de un HashMap .
- Inicialice una variable, digamos ans , para almacenar el mayor número X , de modo que X divida a P pero no sea divisible por Q .
- Iterar a través de todos los divisores de Q y realizar los siguientes pasos:
- Almacene el recuento de frecuencias del divisor primo actual en una variable, por ejemplo, frecuencia .
- Almacene el conteo de frecuencias del divisor primo actual al dividir P en una variable, digamos cur , e inicialice num como el divisor primo actual * (frecuencia – cur + 1) .
- Si el valor de cur es menor que la frecuencia , actualice la variable ans a P y salga del ciclo .
- De lo contrario, divida P con num y almacene el resultado en una variable, digamos tempAns .
- Después de completar los pasos anteriores, actualice el valor de ans al máximo de ans y tempAns .
- Después de completar los pasos anteriores, imprima el valor de ans como el resultado máximo posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the largest number
// X such that it divides P but is not
// divisible by Q
void findTheGreatestX(int P, int Q)
{
// Stores the frequency count of
// of all Prime Factors
map<int, int> divisors;
for (int i = 2; i * i <= Q; i++) {
while (Q % i == 0 and Q > 1) {
Q /= i;
// Increment the frequency
// of the current prime factor
divisors[i]++;
}
}
// If Q is a prime factor
if (Q > 1)
divisors[Q]++;
// Stores the desired result
int ans = 0;
// Iterate through all divisors of Q
for (auto i : divisors) {
int frequency = i.second;
int temp = P;
// Stores the frequency count
// of current prime divisor on
// dividing P
int cur = 0;
while (temp % i.first == 0) {
temp /= i.first;
// Count the frequency of the
// current prime factor
cur++;
}
// If cur is less than frequency
// then P is the final result
if (cur < frequency) {
ans = P;
break;
}
temp = P;
// Iterate to get temporary answer
for (int j = cur; j >= frequency; j--) {
temp /= i.first;
}
// Update current answer
ans = max(temp, ans);
}
// Print the desired result
cout << ans;
}
// Driver Code
int main()
{
// Given P and Q
int P = 10, Q = 4;
// Function Call
findTheGreatestX(P, Q);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the largest number
// X such that it divides P but is not
// divisible by Q
static void findTheGreatestX(int P, int Q)
{
// Stores the frequency count of
// of all Prime Factors
HashMap<Integer, Integer> divisors = new HashMap<>();
for(int i = 2; i * i <= Q; i++)
{
while (Q % i == 0 && Q > 1)
{
Q /= i;
// Increment the frequency
// of the current prime factor
if (divisors.containsKey(i))
{
divisors.put(i, divisors.get(i) + 1);
}
else
{
divisors.put(i, 1);
}
}
}
// If Q is a prime factor
if (Q > 1)
if (divisors.containsKey(Q))
{
divisors.put(Q, divisors.get(Q) + 1);
}
else
{
divisors.put(Q, 1);
}
// Stores the desired result
int ans = 0;
// Iterate through all divisors of Q
for(Map.Entry<Integer, Integer> i : divisors.entrySet())
{
int frequency = i.getValue();
int temp = P;
// Stores the frequency count
// of current prime divisor on
// dividing P
int cur = 0;
while (temp % i.getKey() == 0)
{
temp /= i.getKey();
// Count the frequency of the
// current prime factor
cur++;
}
// If cur is less than frequency
// then P is the final result
if (cur < frequency)
{
ans = P;
break;
}
temp = P;
// Iterate to get temporary answer
for(int j = cur; j >= frequency; j--)
{
temp /= i.getKey();
}
// Update current answer
ans = Math.max(temp, ans);
}
// Print the desired result
System.out.print(ans);
}
// Driver Code
public static void main(String[] args)
{
// Given P and Q
int P = 10, Q = 4;
// Function Call
findTheGreatestX(P, Q);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to implement # the above approach from collections import defaultdict # Function to find the largest number # X such that it divides P but is not # divisible by Q def findTheGreatestX(P, Q): # Stores the frequency count of # of all Prime Factors divisors = defaultdict(int) i = 2 while i * i <= Q: while (Q % i == 0 and Q > 1): Q //= i # Increment the frequency # of the current prime factor divisors[i] += 1 i += 1 # If Q is a prime factor if (Q > 1): divisors[Q] += 1 # Stores the desired result ans = 0 # Iterate through all divisors of Q for i in divisors: frequency = divisors[i] temp = P # Stores the frequency count # of current prime divisor on # dividing P cur = 0 while (temp % i == 0): temp //= i # Count the frequency of the # current prime factor cur += 1 # If cur is less than frequency # then P is the final result if (cur < frequency): ans = P break temp = P # Iterate to get temporary answer for j in range(cur, frequency-1, -1): temp //= i # Update current answer ans = max(temp, ans) # Print the desired result print(ans) # Driver Code if __name__ == "__main__": # Given P and Q P = 10 Q = 4 # Function Call findTheGreatestX(P, Q) # This code is contributed by chitranayal
C#
// C# program to implement
// the above approach
using System.Collections.Generic;
using System;
using System.Linq;
class GFG{
// Function to find the largest number
// X such that it divides P but is not
// divisible by Q
static void findTheGreatestX(int P, int Q)
{
// Stores the frequency count of
// of all Prime Factors
Dictionary<int,
int> divisers = new Dictionary<int,
int>();
for(int i = 2; i * i <= Q; i++)
{
while (Q % i == 0 && Q > 1)
{
Q /= i;
// Increment the frequency
// of the current prime factor
if (divisers.ContainsKey(i))
divisers[i]++;
else
divisers[i] = 1;
}
}
// If Q is a prime factor
if (Q > 1)
{
if (divisers.ContainsKey(Q))
divisers[Q]++;
else
divisers[Q] = 1;
}
// Stores the desired result
int ans = 0;
var val = divisers.Keys.ToList();
// Iterate through all divisors of Q
foreach(var key in val)
{
int frequency = divisers[key];
int temp = P;
// Stores the frequency count
// of current prime divisor on
// dividing P
int cur = 0;
while (temp % key == 0)
{
temp /= key;
// Count the frequency of the
// current prime factor
cur++;
}
// If cur is less than frequency
// then P is the final result
if (cur < frequency)
{
ans = P;
break;
}
temp = P;
// Iterate to get temporary answer
for(int j = cur; j >= frequency; j--)
{
temp /= key;
}
// Update current answer
ans = Math.Max(temp, ans);
}
// Print the desired result
Console.WriteLine(ans);
}
// Driver Code
public static void Main(String[] args)
{
// Given P and Q
int P = 10, Q = 4;
// Function Call
findTheGreatestX(P, Q);
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the largest number
// X such that it divides P but is not
// divisible by Q
function findTheGreatestX(P, Q)
{
// Stores the frequency count of
// of all Prime Factors
var divisors = new Map();
for(var i = 2; i * i <= Q; i++)
{
while (Q % i == 0 && Q > 1)
{
Q = parseInt(Q / i);
// Increment the frequency
// of the current prime factor
if (divisors.has(i))
divisors.set(i, divisors.get(i) + 1)
else
divisors.set(i, 1)
}
}
// If Q is a prime factor
if (Q > 1)
if (divisors.has(Q))
divisors.set(Q, divisors.get(Q) + 1)
else
divisors.set(Q, 1)
// Stores the desired result
var ans = 0;
// Iterate through all divisors of Q
divisors.forEach((value, key) => {
var frequency = value;
var temp = P;
// Stores the frequency count
// of current prime divisor on
// dividing P
var cur = 0;
while (temp % key == 0)
{
temp = parseInt(temp / key);
// Count the frequency of the
// current prime factor
cur++;
}
// If cur is less than frequency
// then P is the final result
if (cur < frequency)
{
ans = P;
}
temp = P;
// Iterate to get temporary answer
for(var j = cur; j >= frequency; j--)
{
temp = parseInt(temp / key);
}
// Update current answer
ans = Math.max(temp, ans);
});
// Print the desired result
document.write(ans);
}
// Driver Code
// Given P and Q
var P = 10, Q = 4;
// Function Call
findTheGreatestX(P, Q);
// This code is contributed by itsok
</script>
Producción
10
Complejidad de tiempo: O(sqrt(Q) + log(P) * log(Q))
Espacio auxiliar: O(Q)
Publicación traducida automáticamente
Artículo escrito por reapedjuggler y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA