Dada una array de enteros arr[] de tamaño N y un entero K , la tarea es encontrar el primo más pequeño tal que dé el resto K cuando se divide por cualquiera de los elementos de la array.
Nota: El número primo debe estar en el rango [1, 10 6 ]
Ejemplos:
Entrada: arr[]= {3, 4, 5}, K = 1
Salida : 61
Explicación: El primo más pequeño que satisface la condición es 61.
61%3 = 1, 61%4 = 1 y 61%5 =1.Entrada: arr[] = {2, 4, 5}, K = 3
Salida: -1
Explicación: La salida no debería ser posible porque
ningún número puede tener resto 3 cuando se divide por 2.Entrada: arr[] = {10, 4, 5}, K = 3
Salida: 23
Explicación: El primo más pequeño que satisface la condición es 23.
23%10 = 3, 23%4 = 3 y 23%5 = 3
Planteamiento: La idea para resolver el problema se menciona a continuación:
Si algún elemento de la array es más pequeño que K, entonces la solución no es posible. Porque ningún número puede tener un resto mayor que él mismo al dividir un número.
El MCM de los números es el número más pequeño divisible por todos los demás números. Así que encuentre el MCM de la array y verifique para cada múltiplo del MCM si LCM + K es primo o no para obtener el primo más pequeño que da el resto como K.
Siga los pasos a continuación para lo anterior:
- Primero verifique, si el elemento mínimo de la array es menor que k {es decir; min(arr)>=K} , entonces la solución no es posible, luego devuelve -1
- Encuentre el mcm de todos los elementos de la array (por ejemplo, mcm).
- Iterar por cada múltiplo de mcm que sea menor o igual a 10 6 :
- Comprueba si ( mcm + K ) es primo o no para cada múltiplo de mcm
- Si la condición se cumple, devuelve la suma de K y el múltiplo actual de mcm como el primo_más pequeño.
- Si no encuentra ningún número primo, devuelva -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// gcd of two integers
long long gcd(long long int a,
long long int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to check if an integer
// is prime or not
bool checkPrime(long long n)
{
long long ub = sqrt(n);
for (long long i = 2; i <= ub; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
// Function to find the smallest prime
// that gives the same remainder when
// divided by any of the element in arr.
long long smallestPrime(vector<int> arr,
int q)
{
// Finding the lcm of the array
long long lcm = arr[0];
for (int i : arr) {
lcm = (lcm * i) / (gcd(i, lcm));
}
// Edge case, if the value of any
// in the array is less than remainder
for (auto i : arr) {
if (i < q)
return -1;
}
// Check whether (lcm + remainder) is
// prime or not, for all multiples of lcm
for (long long i = lcm; i <= 1e9;
i += lcm) {
if (checkPrime(i + q)) {
return i + q;
}
}
// If any prime satisfying the
// condition is not found
// simply return -1;
return -1;
}
// Driver code
int main()
{
vector<int> arr = { 2, 5, 4 };
int q = 3;
cout << smallestPrime(arr, q);
return 0;
}
Java
// Java code for the above approach
import java.io.*;
class GFG {
// Function to find the
// gcd of two integers
public static long gcd(long a, long b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to check if an integer
// is prime or not
public static boolean checkPrime(long n)
{
long ub = (long)Math.sqrt(n);
for (int i = 2; i <= ub; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
// Function to find the smallest prime
// that gives the same remainder when
// divided by any of the element in arr.
public static long smallestPrime(int arr[], int q)
{
// Finding the lcm of the array
long lcm = (long)arr[0];
for (int i : arr) {
lcm =(long)(lcm * (long)i) / (long)(gcd((long)i,(long)lcm));
}
// Edge case, if the value of any
// in the array is less than remainder
for (int i : arr) {
if (i < q)
return -1;
}
// Check whether (lcm + remainder) is
// prime or not, for all multiples of lcm
for (long i = lcm; i <= 1e9; i += lcm) {
if (checkPrime(i + q)) {
return i + q;
}
}
// If any prime satisfying the
// condition is not found
// simply return -1;
return -1;
}
public static void main(String[] args)
{
int arr[] = { 2, 5, 4 };
int q = 3;
System.out.print(smallestPrime(arr, q));
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python code for the above approach import math # Function to find the # gcd of two integers def gcd( a, b): if b == 0: return a; return gcd(b, a % b); # Function to check if an integer # is prime or not def checkPrime(n): ub = math.sqrt(n); for i in range(2,ub): if (n % i == 0): return 0; return 1; # Function to find the smallest prime # that gives the same remainder when # divided by any of the element in arr. def smallestPrime(arr, q): # Finding the lcm of the array lcm = arr[0]; for i in range(len(arr)): lcm = (lcm * i) / (gcd(arr[i], lcm)); # Edge case, if the value of any # in the array is less than remainder for i in range(len(arr)): if (arr[i] < q): return -1; # Check whether (lcm + remainder) is # prime or not, for all multiples of lcm for i in range(lcm, 1e9, lcm): if (checkPrime(i + q)): return i + q; # If any prime satisfying the # condition is not found # simply return -1; return -1; # Driver code arr = [2, 5, 4]; q = 3; print(smallestPrime(arr, q)); # This code is contributed by Potta Lokesh
C#
// C# code for the above approach
using System;
class GFG {
// Function to find the
// gcd of two integers
static long gcd(long a, long b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to check if an integer
// is prime or not
static bool checkPrime(long n)
{
long ub = (long)Math.Sqrt(n);
for (int i = 2; i <= ub; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
// Function to find the smallest prime
// that gives the same remainder when
// divided by any of the element in arr.
static long smallestPrime(int []arr, int q)
{
// Finding the lcm of the array
long lcm = (long)arr[0];
for (int i = 0; i < arr.Length; i++) {
lcm =(long)(lcm * (long)arr[i]) / (long)(gcd((long)arr[i],(long)lcm));
}
// Edge case, if the value of any
// in the array is less than remainder
for (int i = 0; i < arr.Length; i++) {
if (arr[i] < q)
return -1;
}
// Check whether (lcm + remainder) is
// prime or not, for all multiples of lcm
for (long i = lcm; i <= 1e9; i += lcm) {
if (checkPrime(i + q)) {
return i + q;
}
}
// If any prime satisfying the
// condition is not found
// simply return -1;
return -1;
}
public static void Main()
{
int []arr = { 2, 5, 4 };
int q = 3;
Console.Write(smallestPrime(arr, q));
}
}
// This code is contributed by Samim Hossain Mondal
Javascript
<script>
// JavaScript code for the above approach
// Function to find the
// gcd of two integers
function gcd(a, b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to check if an integer
// is prime or not
function checkPrime(n)
{
ub = Math.Sqrt(n);
for (var i = 2; i <= ub; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
// Function to find the smallest prime
// that gives the same remainder when
// divided by any of the element in arr.
function smallestPrime(arr, q)
{
// Finding the lcm of the array
var lcm = arr[0];
for (const i of arr) {
lcm = (lcm * i) / (gcd(i, lcm));
}
// Edge case, if the value of any
// in the array is less than remainder
for (const i of arr) {
if (i < q)
return -1;
}
// Check whether (lcm + remainder) is
// prime or not, for all multiples of lcm
for (var i = lcm; i <= 1000000000; i += lcm) {
if (checkPrime(i + q)) {
return i + q;
}
}
// If any prime satisfying the
// condition is not found
// simply return -1;
return -1;
}
// Driver code
var arr = [ 2, 5, 4 ];
var q = 3;
document.write(smallestPrime(arr, q));
// This code is contributed by phasing17
</script>
-1
Complejidad de tiempo: O(N * logD + (M/lcm)*sqrt(M)) donde D es el máximo de la array, M es el límite superior posible del primo, lcm es el LCM de todos los elementos de la array Espacio auxiliar: O(
1 )
Publicación traducida automáticamente
Artículo escrito por prathamjha5683 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA