Dada una array arr[] de N enteros, la tarea es encontrar el divisor más grande para cada elemento de una array que no sea 1 y el número en sí. Si no existe tal divisor, imprima -1.
Ejemplos:
Entrada: arr[] = {5, 6, 7, 8, 9, 10}
Salida: -1 3 -1 4 3 5
Divisores(5) = {1, 5}
-> Como no hay otro divisor que no sea 1 y el número en sí, por lo tanto, el divisor más grande = -1
Divisores (6) = [1, 2, 3, 6]
-> el divisor más grande que no sea 1 y el número en sí = 3
Divisores (7) = [1, 7]
-> Dado que no hay otro divisor que no sea 1 y el número en sí, por lo tanto el divisor más grande = -1
Divisores(8) = [1, 2, 4, 8]
-> el divisor más grande que no sea 1 y el número en sí = 4
Divisores(9) = [1, 3, 9]
-> divisor más grande que no sea 1 y el número en sí = 3
Divisores (10) = [1, 2, 5, 10]
-> divisor más grande que no sea 1 y el número en sí = 5Entrada: arr[] = {15, 16, 17, 18, 19, 20, 21}
Salida: 5 8 -1 9 -1 10 7
Enfoque ingenuo: la idea es iterar sobre todos los elementos de la array y encontrar el divisor más grande para cada uno de los elementos usando el enfoque discutido en este artículo.
Complejidad temporal: O(N * √N)
Enfoque eficiente: una mejor solución es precalcular el divisor máximo de los números de 2 a 10 5 y luego simplemente ejecutar un bucle para la array e imprimir la respuesta precalculada.
- Usa la criba de Eratóstenes para marcar los números primos y almacenar el divisor primo más pequeño de cada número.
- Ahora el divisor más grande para cualquier número será número / más pequeño_primo_divisor .
- Encuentra el divisor más grande para cada número usando la respuesta precalculada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxin = 100001;
// Divisors array to keep track
// of the maximum divisor
int divisors[maxin];
// Function to pre-compute the prime
// numbers and largest divisors
void Calc_Max_Div(int arr[], int n)
{
// Visited array to keep
// track of prime numbers
bool vis[maxin];
memset(vis, 1, maxin);
// 0 and 1 are not prime numbers
vis[0] = vis[1] = 0;
// Initialising divisors[i] = i
for (int i = 1; i <= maxin; i++)
divisors[i] = i;
// For all the numbers divisible by 2
// the maximum divisor will be number / 2
for (int i = 4; i <= maxin; i += 2) {
vis[i] = 0;
divisors[i] = i / 2;
}
for (int i = 3; i <= maxin; i += 2) {
// If divisors[i] is not equal to i then
// this means that divisors[i] contains
// minimum prime divisor for the number
if (divisors[i] != i) {
// Update the answer to
// i / smallest_prime_divisor[i]
divisors[i] = i / divisors[i];
}
// Condition if i is a prime number
if (vis[i] == 1) {
for (int j = i * i; j < maxin; j += i) {
vis[j] = 0;
// If divisors[j] is equal to j then
// this means that i is the first prime
// divisor for j so we update divi[j] = i
if (divisors[j] == j)
divisors[j] = i;
}
}
}
for (int i = 0; i < n; i++) {
// If the current element is prime
// then it has no divisors
// other than 1 and itself
if (divisors[arr[i]] == arr[i])
cout << "-1 ";
else
cout << divisors[arr[i]] << " ";
}
}
// Driver code
int32_t main()
{
int arr[] = { 5, 6, 7, 8, 9, 10 };
int n = sizeof(arr) / sizeof(int);
Calc_Max_Div(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
final static int maxin = 10001;
// Divisors array to keep track
// of the maximum divisor
static int divisors[] = new int[maxin + 1];
// Function to pre-compute the prime
// numbers and largest divisors
static void Calc_Max_Div(int arr[], int n)
{
// Visited array to keep
// track of prime numbers
int vis[] = new int[maxin + 1];
for(int i = 0;i <maxin+1 ; i++)
vis[i] = 1;
// 0 and 1 are not prime numbers
vis[0] = vis[1] = 0;
// Initialising divisors[i] = i
for (int i = 1; i <= maxin; i++)
divisors[i] = i;
// For all the numbers divisible by 2
// the maximum divisor will be number / 2
for (int i = 4; i <= maxin; i += 2)
{
vis[i] = 0;
divisors[i] = i / 2;
}
for (int i = 3; i <= maxin; i += 2)
{
// If divisors[i] is not equal to i then
// this means that divisors[i] contains
// minimum prime divisor for the number
if (divisors[i] != i)
{
// Update the answer to
// i / smallest_prime_divisor[i]
divisors[i] = i / divisors[i];
}
// Condition if i is a prime number
if (vis[i] == 1)
{
for (int j = i * i; j < maxin; j += i)
{
vis[j] = 0;
// If divisors[j] is equal to j then
// this means that i is the first prime
// divisor for j so we update divi[j] = i
if (divisors[j] == j)
divisors[j] = i;
}
}
}
for (int i = 0; i < n; i++)
{
// If the current element is prime
// then it has no divisors
// other than 1 and itself
if (divisors[arr[i]] == arr[i])
System.out.print("-1 ");
else
System.out.print(divisors[arr[i]] + " ");
}
}
// Driver code
public static void main (String[] args)
{
int []arr = { 5, 6, 7, 8, 9, 10 };
int n = arr.length;
Calc_Max_Div(arr, n);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach
maxin = 100001;
# Divisors array to keep track
# of the maximum divisor
divisors = [0] * (maxin + 1);
# Function to pre-compute the prime
# numbers and largest divisors
def Calc_Max_Div(arr, n) :
# Visited array to keep
# track of prime numbers
vis = [1] * (maxin + 1);
# 0 and 1 are not prime numbers
vis[0] = vis[1] = 0;
# Initialising divisors[i] = i
for i in range(1, maxin + 1) :
divisors[i] = i;
# For all the numbers divisible by 2
# the maximum divisor will be number / 2
for i in range(4 , maxin + 1, 2) :
vis[i] = 0;
divisors[i] = i // 2;
for i in range(3, maxin + 1, 2) :
# If divisors[i] is not equal to i then
# this means that divisors[i] contains
# minimum prime divisor for the number
if (divisors[i] != i) :
# Update the answer to
# i / smallest_prime_divisor[i]
divisors[i] = i // divisors[i];
# Condition if i is a prime number
if (vis[i] == 1) :
for j in range( i * i, maxin, i) :
vis[j] = 0;
# If divisors[j] is equal to j then
# this means that i is the first prime
# divisor for j so we update divi[j] = i
if (divisors[j] == j) :
divisors[j] = i;
for i in range(n) :
# If the current element is prime
# then it has no divisors
# other than 1 and itself
if (divisors[arr[i]] == arr[i]) :
print("-1 ", end = "");
else :
print(divisors[arr[i]], end = " ");
# Driver code
if __name__ == "__main__" :
arr = [ 5, 6, 7, 8, 9, 10 ];
n = len(arr);
Calc_Max_Div(arr, n);
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int maxin = 10001;
// Divisors array to keep track
// of the maximum divisor
static int []divisors = new int[maxin + 1];
// Function to pre-compute the prime
// numbers and largest divisors
static void Calc_Max_Div(int []arr, int n)
{
// Visited array to keep
// track of prime numbers
int []vis = new int[maxin + 1];
for(int i = 0; i < maxin + 1 ; i++)
vis[i] = 1;
// 0 and 1 are not prime numbers
vis[0] = vis[1] = 0;
// Initialising divisors[i] = i
for (int i = 1; i <= maxin; i++)
divisors[i] = i;
// For all the numbers divisible by 2
// the maximum divisor will be number / 2
for (int i = 4; i <= maxin; i += 2)
{
vis[i] = 0;
divisors[i] = i / 2;
}
for (int i = 3; i <= maxin; i += 2)
{
// If divisors[i] is not equal to i then
// this means that divisors[i] contains
// minimum prime divisor for the number
if (divisors[i] != i)
{
// Update the answer to
// i / smallest_prime_divisor[i]
divisors[i] = i / divisors[i];
}
// Condition if i is a prime number
if (vis[i] == 1)
{
for (int j = i * i; j < maxin; j += i)
{
vis[j] = 0;
// If divisors[j] is equal to j then
// this means that i is the first prime
// divisor for j so we update divi[j] = i
if (divisors[j] == j)
divisors[j] = i;
}
}
}
for (int i = 0; i < n; i++)
{
// If the current element is prime
// then it has no divisors
// other than 1 and itself
if (divisors[arr[i]] == arr[i])
Console.Write("-1 ");
else
Console.Write(divisors[arr[i]] + " ");
}
}
// Driver code
public static void Main()
{
int []arr = { 5, 6, 7, 8, 9, 10 };
int n = arr.Length;
Calc_Max_Div(arr, n);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
var maxin = 100001;
// Divisors array to keep track
// of the maximum divisor
var divisors = Array(maxin).fill(0);
// Function to pre-compute the prime
// numbers and largest divisors
function Calc_Max_Div(arr, n)
{
// Visited array to keep
// track of prime numbers
var vis = Array(maxin).fill(1);
// 0 and 1 are not prime numbers
vis[0] = vis[1] = 0;
var i,j;
// Initialising divisors[i] = i
for(i = 1; i <= maxin; i++)
divisors[i] = i;
// For all the numbers divisible by 2
// the maximum divisor will be number / 2
for(i = 4; i <= maxin; i += 2)
{
vis[i] = 0;
divisors[i] = i / 2;
}
for(i = 3; i <= maxin; i += 2)
{
// If divisors[i] is not equal to i then
// this means that divisors[i] contains
// minimum prime divisor for the number
if (divisors[i] != i)
{
// Update the answer to
// i / smallest_prime_divisor[i]
divisors[i] = i / divisors[i];
}
// Condition if i is a prime number
if (vis[i] == 1)
{
for(j = i * i; j < maxin; j += i)
{
vis[j] = 0;
// If divisors[j] is equal to j then
// this means that i is the first prime
// divisor for j so we update divi[j] = i
if (divisors[j] == j)
divisors[j] = i;
}
}
}
for(i = 0; i < n; i++)
{
// If the current element is prime
// then it has no divisors
// other than 1 and itself
if (divisors[arr[i]] == arr[i])
document.write("-1 ");
else
document.write(divisors[arr[i]] + " ");
}
}
// Driver code
var arr = [ 5, 6, 7, 8, 9, 10 ];
var n = arr.length;
Calc_Max_Div(arr, n);
// This code is contributed by bgangwar59
</script>
Producción:
-1 3 -1 4 3 5
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(100001)
Publicación traducida automáticamente
Artículo escrito por KushagraPathak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA