Dados dos enteros positivos N y M ., la tarea es encontrar el divisor más pequeño D de N tal que mcd(D, M) > 1 . Si no hay tales divisores, imprima -1.
Ejemplos:
Entrada: N = 8, M = 10
Salida: 2
Entrada: N = 8, M = 1
Salida: -1
Un enfoque ingenuo es iterar para cada factor y calcular el gcd del factor y M. Si excede M, entonces tenemos la respuesta.
Complejidad de tiempo: O (N * log max (N, M))
Un enfoque eficiente es iterar hasta sqrt (n) y verificar gcd (i, m). Si gcd(i, m) > 1, lo imprimimos y lo separamos, de lo contrario buscamos gcd(n/i, m) y almacenamos el mínimo de ellos.
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;
// Function to find the minimum divisor
int findMinimum(int n, int m)
{
int mini = m;
// Iterate for all factors of N
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
int sec = n / i;
// Check for gcd > 1
if (__gcd(m, i) > 1) {
return i;
}
// Check for gcd > 1
else if (__gcd(sec, m) > 1) {
mini = min(sec, mini);
}
}
}
// If gcd is m itself
if (mini == m)
return -1;
else
return mini;
}
// Drivers code
int main()
{
int n = 8, m = 10;
cout << findMinimum(n, m);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
static int __gcd(int a, int b)
{
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Function to find the minimum divisor
static int findMinimum(int n, int m)
{
int mini = m;
// Iterate for all factors of N
for (int i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
int sec = n / i;
// Check for gcd > 1
if (__gcd(m, i) > 1)
{
return i;
}
// Check for gcd > 1
else if (__gcd(sec, m) > 1)
{
mini = Math.min(sec, mini);
}
}
}
// If gcd is m itself
if (mini == m)
return -1;
else
return mini;
}
// Driver code
public static void main (String[] args)
{
int n = 8, m = 10;
System.out.println(findMinimum(n, m));
}
}
// This code is contributed by chandan_jnu
Python3
# Python3 implementation of the above approach import math # Function to find the minimum divisor def findMinimum(n, m): mini, i = m, 1 # Iterate for all factors of N while i * i <= n: if n % i == 0: sec = n // i # Check for gcd > 1 if math.gcd(m, i) > 1: return i # Check for gcd > 1 elif math.gcd(sec, m) > 1: mini = min(sec, mini) i += 1 # If gcd is m itself if mini == m: return -1 else: return mini # Drivers code if __name__ == "__main__": n, m = 8, 10 print(findMinimum(n, m)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the above approach
using System;
class GFG
{
static int __gcd(int a, int b)
{
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Function to find the minimum divisor
static int findMinimum(int n, int m)
{
int mini = m;
// Iterate for all factors of N
for (int i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
int sec = n / i;
// Check for gcd > 1
if (__gcd(m, i) > 1)
{
return i;
}
// Check for gcd > 1
else if (__gcd(sec, m) > 1)
{
mini = Math.Min(sec, mini);
}
}
}
// If gcd is m itself
if (mini == m)
return -1;
else
return mini;
}
// Driver code
static void Main()
{
int n = 8, m = 10;
Console.WriteLine(findMinimum(n, m));
}
}
// This code is contributed by chandan_jnu
PHP
<?php
// PHP implementation of the above approach
function __gcd($a, $b)
{
if ($b == 0)
return $a;
return __gcd($b, $a % $b);
}
// Function to find the minimum divisor
function findMinimum($n, $m)
{
$mini = $m;
// Iterate for all factors of N
for ($i = 1; $i * $i <= $n; $i++)
{
if ($n % $i == 0)
{
$sec = $n / $i;
// Check for gcd > 1
if (__gcd($m, $i) > 1)
{
return $i;
}
// Check for gcd > 1
else if (__gcd($sec, $m) > 1)
{
$mini = min($sec, $mini);
}
}
}
// If gcd is m itself
if ($mini == $m)
return -1;
else
return $mini;
}
// Driver code
$n = 8; $m = 10;
echo(findMinimum($n, $m));
// This code is contributed by Code_Mech.
Javascript
<script>
// javascript implementation of the above approach
function __gcd(a , b) {
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Function to find the minimum divisor
function findMinimum(n , m) {
var mini = m;
// Iterate for all factors of N
for (var i = 1; i * i <= n; i++) {
if (n % i == 0) {
var sec = n / i;
// Check for gcd > 1
if (__gcd(m, i) > 1) {
return i;
}
// Check for gcd > 1
else if (__gcd(sec, m) > 1) {
mini = Math.min(sec, mini);
}
}
}
// If gcd is m itself
if (mini == m)
return -1;
else
return mini;
}
// Driver code
var n = 8, m = 10;
document.write(findMinimum(n, m));
// This code is contributed by todaysgaurav
</script>
2
Complejidad de tiempo: O(sqrt(N) * log max(N, M)), ya que estamos usando un ciclo para atravesar sqrt(N) veces y estamos usando la función GCD incorporada en cada recorrido que cuesta logN tiempo. Donde N y M son los dos números enteros proporcionados.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.