Dados dos enteros n y m, la tarea es encontrar un número p que satisfaga las siguientes condiciones:
-> El número p debe ser menor o igual que n.
-> El número debe ser coprimo con todos los números enteros del 2 al p (inclusive), es decir, el único número entero positivo que divide a ambos números es 1.
Ejemplos:
Input : n = 16, m = 3
Output : 13
Explanation : We need to find largest number
smaller than n and co-prime with all numbers
in set [2, 3, ... m] which is [2, 3] here.
Note that numbers {2, 4, 6, 8, ..} are not
co-prime with 2 and numbers {3, 6, 9, .. }
are not co-prime with 3.
Input : n = 6, m = 5
Output : -1 (Number doesn't exists)
Explanation : In this example 2 will cancel
out 2, 4, 6 and 3 will cancel out 3, 6
and 5 will cancel out 5. No number is left,
so the answer does not exists.
Enfoque 1: Cree una lista de números del 2 al n. Y luego ejecuta un bucle de i = 2 a m y marca todos los números que son múltiplos de i. Si i ya está marcado, no ejecute el bucle ya que sus múltiplos ya estarán marcados. Cuando el ciclo termina, ejecute un ciclo de n a 2 hasta que se encuentre un número sin marcar. El primer número sin marcar es la respuesta, si no hay ningún número sin marcar, entonces el número no existe. Este enfoque ocupa el espacio auxiliar O(n), por lo que si el valor de n es demasiado grande, este método no funcionará.
Enfoque 2: Ejecute un ciclo de n a p+1 y verifique cada número si no es divisible por ningún número entre 2 y m.
C++
#include <bits/stdc++.h>
using namespace std;
// Returns true if i is co-prime with numbers
// in set [2, 3, ... m]
bool isValid(long long int i, long long int m)
{
// Running the loop till square root of n
// to reduce the time complexity from n
long long int sq_i = sqrt(i);
// Find the minimum of square root of n
// and m to run the loop until the smaller
// one
long long int sq = min(m, sq_i);
// Check from 2 to min(m, sqrt(n))
for (long long int j = 2; j <= sq; j++)
if (i % j == 0)
return false;
return true;
}
// Function to find the largest number less than n
// which is Co-prime with all numbers from 2 to m
void findLargestNum(long long int n, long long int m)
{
// Iterating from n to m+1 to find the number
for (long long int i = n; i > m; i--) {
// checking every number for the given
// conditions
if (isValid(i, m)) {
// The first number which satisfy the
// conditions is the answer
cout << i << '\n';
return;
}
}
// If there is no number which satisfy the
// conditions, then print number does not exist.
cout << "Number Doesn't Exists\n";
}
// Driver Program
int main()
{
long long int n = 16, m = 3;
findLargestNum(n, m);
return 0;
}
Java
// Java Largest number in [2, 3, .. n]
// which is co-prime with numbers
// in [2, 3, .. m]
import java.io.*;
class GFG
{
// Returns true if i is co-prime with numbers
// in set [2, 3, ... m]
static boolean isValid(long i, long m)
{
// Running the loop till square root of n
// to reduce the time complexity from n
long sq_i = (long)Math.sqrt(i);
// Find the minimum of square root of n
// and m to run the loop until the smaller
// one
long sq = Math.min(m, sq_i);
// Check from 2 to min(m, sqrt(n))
for (long j = 2; j <= sq; j++)
if (i % j == 0)
return false;
return true;
}
// Function to find the largest number less than n
// which is Co-prime with all numbers from 2 to m
static void findLargestNum(long n, long m)
{
// Iterating from n to m+1 to find the number
for (long i = n; i > m; i--) {
// checking every number for the given
// conditions
if (isValid(i, m)) {
// The first number which satisfy the
// conditions is the answer
System.out.println (i);
return;
}
}
// If there is no number which satisfy the
// conditions, then print number does not exist.
System.out.println("Number Doesn't Exists");
}
// Driver Program
public static void main (String[] args)
{
long n = 16, m = 3;
findLargestNum(n, m);
}
}
// This code is contributed by vt_m.
Python3
# Python3 code to find
# Largest number in
# [2, 3, .. n] which is
# co-prime with
# numbers in [2, 3, .. m]
import math
# Returns true if i is
# co-prime with numbers
# in set [2, 3, ... m]
def isValid(i,m) :
# Running the loop
# till square root of n
# to reduce the time
# complexity from n
sq_i = math.sqrt(i)
# Find the minimum of
# square root of n
# and m to run the loop
# until the smaller
# one
sq = min(m, sq_i)
# Check from 2 to
# min(m, sqrt(n))
for j in range(2, sq + 1) :
if (i % j == 0) :
return False
return True
# def to find the
# largest number less
# than n which is Co-prime
# with all numbers from
# 2 to m
def findLargestNum(n, m) :
# Iterating from n to m+1
# to find the number
for i in range(n, m, -1) :
# checking every number for
# the given conditions
if (isValid(i, m)) :
# The first number
# which satisfy the
# conditions is the
# answer
print ("{}\n".format(i));
return
# If there is no number
# which satisfy the
# conditions, then print
# number does not exist.
print ("Number Doesn't Exists\n")
# Driver Code
n = 16
m = 3
findLargestNum(n, m)
# This code is contributed by
# Manish Shaw(manishshaw1)
C#
// C# Largest number in [2, 3, .. n]
// which is co-prime with numbers
// in [2, 3, .. m]
using System;
class GFG
{
// Returns true if i is co-prime
// with numbers in set [2, 3, ... m]
static bool isValid(long i, long m)
{
// Running the loop till square root
// of n to reduce the time complexity
// from n
long sq_i = (long)Math.Sqrt(i);
// Find the minimum of square root
// of n and m to run the loop until
// the smaller one
long sq = Math.Min(m, sq_i);
// Check from 2 to min(m, sqrt(n))
for (long j = 2; j <= sq; j++)
if (i % j == 0)
return false;
return true;
}
// Function to find the largest number
// less than n which is Co-prime with
// all numbers from 2 to m
static void findLargestNum(long n, long m)
{
// Iterating from n to m+1 to find the
// number
for (long i = n; i > m; i--) {
// checking every number for the given
// conditions
if (isValid(i, m)) {
// The first number which satisfy the
// conditions is the answer
Console.WriteLine(i);
return;
}
}
// If there is no number which satisfy
// the conditions, then print number does
// not exist.
Console.WriteLine("Number Doesn't Exists");
}
// Driver Program
public static void Main ()
{
long n = 55, m = 25;
findLargestNum(n, m);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP code to find Largest number in
// [2, 3, .. n] which is co-prime with
// numbers in [2, 3, .. m]
// Returns true if i is
// co-prime with numbers
// in set [2, 3, ... m]
function isValid($i,$m)
{
// Running the loop
// till square root of n
// to reduce the time
// complexity from n
$sq_i = sqrt($i);
// Find the minimum of
// square root of n
// and m to run the loop
// until the smaller
// one
$sq = min($m, $sq_i);
// Check from 2 to
// min(m, sqrt(n))
for ($j = 2; $j <= $sq; $j++)
if ($i % $j == 0)
return false;
return true;
}
// Function to find the
// largest number less than n
// which is Co-prime with
// all numbers from 2 to m
function findLargestNum($n, $m)
{
// Iterating from n to m+1
// to find the number
for ($i = $n; $i > $m; $i--)
{
// checking every number for
// the given conditions
if (isValid($i, $m))
{
// The first number
// which satisfy the
// conditions is the
// answer
echo $i , "\n";
return;
}
}
// If there is no number
// which satisfy the
// conditions, then print
// number does not exist.
echo "Number Doesn't Exists\n";
}
// Driver Code
$n = 16; $m = 3;
findLargestNum($n, $m);
// This code is contributed by anuj_67
?>
Javascript
<script>
// JavaScript program to find Largest number in [2, 3, .. n]
// which is co-prime with numbers
// in [2, 3, .. m]
// Returns true if i is co-prime with numbers
// in set [2, 3, ... m]
function isValid(i, m)
{
// Running the loop till square root of n
// to reduce the time complexity from n
let sq_i = Math.sqrt(i);
// Find the minimum of square root of n
// and m to run the loop until the smaller
// one
let sq = Math.min(m, sq_i);
// Check from 2 to min(m, sqrt(n))
for (let j = 2; j <= sq; j++)
if (i % j == 0)
return false;
return true;
}
// Function to find the largest number less than n
// which is Co-prime with all numbers from 2 to m
function findLargestNum(n, m)
{
// Iterating from n to m+1 to find the number
for (let i = n; i > m; i--) {
// checking every number for the given
// conditions
if (isValid(i, m)) {
// The first number which satisfy the
// conditions is the answer
document.write (i);
return;
}
}
// If there is no number which satisfy the
// conditions, then print number does not exist.
document.write("Number Doesn't Exists");
}
// Driver Code
let n = 16, m = 3;
findLargestNum(n, m);
// This code is contributed by susmitakundugoaldanga.
</script>
Producción :
13
Publicación traducida automáticamente
Artículo escrito por Gautam Karakoti y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA