Dada una array, arr[], encuentre la subsecuencia más grande tal que el GCD de todas esas subsecuencias sea mayor que 1.
Ejemplos:
Input: 3, 6, 2, 5, 4 Output: 3 Explanation: There are only three elements(6, 2, 4) having GCD greater than 1 i.e., 2. So the largest subsequence will be 3 Input: 10, 15, 7, 25, 9, 35 Output: 4
Enfoque ingenuo (Método 1)
El enfoque simple es generar todas las subsecuencias una por una y luego encontrar el GCD de todo el conjunto generado. El problema de este enfoque es que crece exponencialmente en 2 N
Enfoque iterativo (Método 2)
Si observamos, encontraremos que para que gcd sea mayor que 1, todos estos elementos deben contener un factor común mayor que 1 que divida uniformemente todos estos valores. Entonces, para obtener ese factor, iteramos desde 2 hasta el elemento máximo de la array y luego verificamos la divisibilidad.
C++
// Simple C++ program to find length of
// the largest subsequence with GCD greater
// than 1.
#include<bits/stdc++.h>
using namespace std;
// Returns length of the largest subsequence
// with GCD more than 1.
int largestGCDSubsequence(int arr[], int n)
{
int ans = 0;
// Finding the Maximum value in arr[]
int maxele = *max_element(arr, arr+n);
// Iterate from 2 to maximum possible
// divisor of all give values
for (int i=2; i<=maxele; ++i)
{
int count = 0;
for (int j=0; j<n; ++j)
{
// If we found divisor,
// increment count
if (arr[j]%i == 0)
++count;
}
ans = max(ans, count);
}
return ans;
}
// Driver code
int main()
{
int arr[] = {3, 6, 2, 5, 4};
int size = sizeof(arr) / sizeof(arr[0]);
cout << largestGCDSubsequence(arr, size);
return 0;
}
Java
// Efficient Java program to find length of
// the largest subsequence with GCD greater
// than 1.
import java.util.Arrays;
class GFG {
// Returns length of the largest subsequence
// with GCD more than 1.
static int largestGCDSubsequence(int arr[], int n)
{
int ans = 0;
// Finding the Maximum value in arr[]
int maxele = Arrays.stream(arr).max().getAsInt();;
// Iterate from 2 to maximum possible
// divisor of all give values
for (int i=2; i<=maxele; ++i)
{
int count = 0;
for (int j=0; j<n; ++j)
{
// If we found divisor,
// increment count
if (arr[j]%i == 0)
++count;
}
ans = Math.max(ans, count);
}
return ans;
}
// Driver program to test above
public static void main(String[] args) {
int arr[] = {3, 6, 2, 5, 4};
int size = arr.length;
System.out.println(largestGCDSubsequence(arr, size));
}
}
//this code contributed by Rajput-Ji
Python3
# Simple Python 3 program to find length of # the largest subsequence with GCD greater # than 1. # Returns length of the largest subsequence # with GCD more than 1. def largestGCDSubsequence(arr, n): ans = 0 # Finding the Maximum value in arr[] maxele = max(arr) # Iterate from 2 to maximum possible # divisor of all give values for i in range(2, maxele + 1): count = 0 for j in range(n): # If we found divisor, # increment count if (arr[j] % i == 0): count += 1 ans = max(ans, count) return ans # Driver code if __name__ == '__main__': arr = [3, 6, 2, 5, 4] size = len(arr) print(largestGCDSubsequence(arr, size)) # This code is contributed by Rajput-Ji
C#
// Efficient C# program to find length of
// the largest subsequence with GCD greater
// than 1.
using System;
using System.Linq;
public class GFG {
// Returns length of the largest subsequence
// with GCD more than 1.
static int largestGCDSubsequence(int []arr, int n)
{
int ans = 0;
// Finding the Maximum value in arr[]
int maxele = arr.Max();
// Iterate from 2 to maximum possible
// divisor of all give values
for (int i=2; i<=maxele; ++i)
{
int count = 0;
for (int j=0; j<n; ++j)
{
// If we found divisor,
// increment count
if (arr[j]%i == 0)
++count;
}
ans = Math.Max(ans, count);
}
return ans;
}
// Driver program to test above
public static void Main() {
int []arr = {3, 6, 2, 5, 4};
int size = arr.Length;
Console.Write(largestGCDSubsequence(arr, size));
}
}
//this code contributed by Rajput-Ji
PHP
<?php
// Simple PHP program to find length of
// the largest subsequence with GCD greater
// than 1.
// Returns length of the largest subsequence
// with GCD more than 1.
function largestGCDSubsequence($arr, $n)
{
$ans = 0;
// Finding the Maximum value in arr[]
$maxele = max($arr);
// Iterate from 2 to maximum possible
// divisor of all give values
for ($i = 2; $i <= $maxele; ++$i)
{
$count = 0;
for ($j = 0; $j < $n; ++$j)
{
// If we found divisor,
// increment count
if ($arr[$j] % $i == 0)
++$count;
}
$ans = max($ans, $count);
}
return $ans;
}
// Driver code
$arr = array(3, 6, 2, 5, 4);
$size = count($arr);
echo largestGCDSubsequence($arr, $size);
// This code is contributed by mits
?>
Javascript
<script>
// Efficient javascript program to find length of
// the largest subsequence with GCD greater
// than 1.
// Returns length of the largest subsequence
// with GCD more than 1.
function largestGCDSubsequence(arr , n)
{
var ans = 0;
// Finding the Maximum value in arr
var maxele =Math.max(...arr);
// Iterate from 2 to maximum possible
// divisor of all give values
for ( var i = 2; i <= maxele; ++i)
{
var count = 0;
for (j = 0; j < n; ++j)
{
// If we found divisor,
// increment count
if (arr[j] % i == 0)
++count;
}
ans = Math.max(ans, count);
}
return ans;
}
// Driver program to test above
var arr = [ 3, 6, 2, 5, 4 ];
var size = arr.length;
document.write(largestGCDSubsequence(arr, size));
// This code is contributed by aashish1995
</script>
Producción:
3
Complejidad de tiempo: O(n * max(arr[i])) donde n es el tamaño de la array.
Espacio Auxiliar: O(1)
Mejor enfoque (Método 3)
Un enfoque eficiente es utilizar el método de descomposición en factores primos con la ayuda de la criba de Eratóstenes . En primer lugar, encontraremos el divisor primo más pequeño de todos los elementos mediante un tamiz precalculado. Después de eso, marcaremos todos los divisores primos de cada elemento de arr[] factorizándolos con la ayuda de la array prime[] calculada previamente.
Ahora tenemos todos los primos marcados que ocurren en todos los elementos del arreglo. El último paso es encontrar el recuento máximo de todos esos factores primos.
C++
// Efficient C++ program to find length of
// the largest subsequence with GCD greater
// than 1.
#include<bits/stdc++.h>
using namespace std;
#define MAX 100001
// prime[] for storing smallest prime divisor of element
// count[] for storing the number of times a particular
// divisor occurs in a subsequence
int prime[MAX], countdiv[MAX];
// Simple sieve to find smallest prime factors of numbers
// smaller than MAX
void SieveOfEratosthenes()
{
for (int i = 2; i * i <= MAX; ++i)
{
if (!prime[i])
for (int j = i * 2; j <= MAX; j += i)
prime[j] = i;
}
// Prime number will have same divisor
for (int i = 1; i < MAX; ++i)
if (!prime[i])
prime[i] = i;
}
// Returns length of the largest subsequence
// with GCD more than 1.
int largestGCDSubsequence(int arr[], int n)
{
int ans = 0;
for (int i=0; i < n; ++i)
{
int element = arr[i];
// Fetch total unique prime divisor of element
while (element > 1)
{
int div = prime[element];
// Increment count[] of Every unique divisor
// we get till now
++countdiv[div];
// Find maximum frequency of divisor
ans = max(ans, countdiv[div]);
while (element % div==0)
element /= div;
}
}
return ans;
}
// Driver code
int main()
{
// Pre-compute smallest divisor of all numbers
SieveOfEratosthenes();
int arr[] = {10, 15, 7, 25, 9, 35};
int size = sizeof(arr) / sizeof(arr[0]);
cout << largestGCDSubsequence(arr, size);
return 0;
}
Java
// Efficient Java program to find length of
// the largest subsequence with GCD greater
// than 1.
class GFG
{
static int MAX = 100001;
// prime[] for storing smallest prime divisor
// of element count[] for storing the number
// of times a particular divisor occurs
// in a subsequence
static int[] prime = new int[MAX + 1];
static int[] countdiv = new int[MAX + 1];
// Simple sieve to find smallest prime
// factors of numbers smaller than MAX
static void SieveOfEratosthenes()
{
for (int i = 2; i * i <= MAX; ++i)
{
if (prime[i] == 0)
for (int j = i * 2; j <= MAX; j += i)
prime[j] = i;
}
// Prime number will have same divisor
for (int i = 1; i < MAX; ++i)
if (prime[i] == 0)
prime[i] = i;
}
// Returns length of the largest subsequence
// with GCD more than 1.
static int largestGCDSubsequence(int arr[], int n)
{
int ans = 0;
for (int i = 0; i < n; ++i)
{
int element = arr[i];
// Fetch total unique prime divisor of element
while (element > 1)
{
int div = prime[element];
// Increment count[] of Every unique divisor
// we get till now
++countdiv[div];
// Find maximum frequency of divisor
ans = Math.max(ans, countdiv[div]);
while (element % div == 0)
element /= div;
}
}
return ans;
}
// Driver code
public static void main (String[] args)
{
// Pre-compute smallest divisor of all numbers
SieveOfEratosthenes();
int arr[] = {10, 15, 7, 25, 9, 35};
int size = arr.length;
System.out.println(largestGCDSubsequence(arr, size));
}
}
// This code is contributed by mits
Python3
# Efficient Python3 program to find length # of the largest subsequence with GCD # greater than 1. import math as mt MAX = 100001 # prime[] for storing smallest # prime divisor of element # count[] for storing the number # of times a particular divisor # occurs in a subsequence prime = [0 for i in range(MAX + 1)] countdiv = [0 for i in range(MAX + 1)] # Simple sieve to find smallest prime # factors of numbers smaller than MAX def SieveOfEratosthenes(): for i in range(2, mt.ceil(mt.sqrt(MAX + 1))): if (prime[i] == 0): for j in range(i * 2, MAX + 1, i): prime[j] = i # Prime number will have same divisor for i in range(1, MAX): if (prime[i] == 0): prime[i] = i # Returns length of the largest # subsequence with GCD more than 1. def largestGCDSubsequence(arr, n): ans = 0 for i in range(n): element = arr[i] # Fetch total unique prime # divisor of element while (element > 1): div = prime[element] # Increment count[] of Every # unique divisor we get till now countdiv[div] += 1 # Find maximum frequency of divisor ans = max(ans, countdiv[div]) while (element % div == 0): element = element // div return ans # Driver code # Pre-compute smallest divisor # of all numbers SieveOfEratosthenes() arr= [10, 15, 7, 25, 9, 35] size = len(arr) print(largestGCDSubsequence(arr, size)) # This code is contributed # by Mohit kumar 29
C#
// Efficient C# program to find length of
// the largest subsequence with GCD greater
// than 1.
using System;
class GFG
{
static int MAX=100001;
// prime[] for storing smallest
// prime divisor of element count[]
// for storing the number of times
// a particular divisor occurs in a subsequence
static int[] prime = new int[MAX + 1];
static int[] countdiv = new int[MAX + 1];
// Simple sieve to find smallest prime
// factors of numbers smaller than MAX
static void SieveOfEratosthenes()
{
for (int i = 2; i * i <= MAX; ++i)
{
if (prime[i] == 0)
for (int j = i * 2; j <= MAX; j += i)
prime[j] = i;
}
// Prime number will have same divisor
for (int i = 1; i < MAX; ++i)
if (prime[i] == 0)
prime[i] = i;
}
// Returns length of the largest subsequence
// with GCD more than 1.
static int largestGCDSubsequence(int []arr, int n)
{
int ans = 0;
for (int i = 0; i < n; ++i)
{
int element = arr[i];
// Fetch total unique prime divisor of element
while (element > 1)
{
int div = prime[element];
// Increment count[] of Every unique divisor
// we get till now
++countdiv[div];
// Find maximum frequency of divisor
ans = Math.Max(ans, countdiv[div]);
while (element % div==0)
element /= div;
}
}
return ans;
}
// Driver code
public static void Main()
{
// Pre-compute smallest
// divisor of all numbers
SieveOfEratosthenes();
int []arr = {10, 15, 7, 25, 9, 35};
int size = arr.Length;
Console.WriteLine(largestGCDSubsequence(arr, size));
}
}
// This code is contributed by mits
PHP
<?php
// Efficient PHP program to find length of
// the largest subsequence with GCD greater
// than 1.
$MAX = 10001;
// prime[] for storing smallest prime divisor of element
// count[] for storing the number of times a particular
// divisor occurs in a subsequence
$prime = array_fill(0, $MAX, 0);
$countdiv = array_fill(0, $MAX, 0);
// Simple sieve to find smallest prime factors of numbers
// smaller than MAX
function SieveOfEratosthenes()
{
global $MAX,$prime;
for ($i = 2; $i * $i <= $MAX; ++$i)
{
if ($prime[$i] == 0)
for ($j = $i * 2; $j <= $MAX; $j += $i)
$prime[$j] = $i;
}
// Prime number will have same divisor
for ($i = 1; $i < $MAX; ++$i)
if ($prime[$i] == 0)
$prime[$i] = $i;
}
// Returns length of the largest subsequence
// with GCD more than 1.
function largestGCDSubsequence($arr, $n)
{
global $countdiv,$prime;
$ans = 0;
for ($i = 0; $i < $n; ++$i)
{
$element = $arr[$i];
// Fetch total unique prime divisor of element
while ($element > 1)
{
$div = $prime[$element];
// Increment count[] of Every unique divisor
// we get till now
++$countdiv[$div];
// Find maximum frequency of divisor
$ans = max($ans, $countdiv[$div]);
while ($element % $div == 0)
$element = (int)($element/$div);
}
}
return $ans;
}
// Driver code
// Pre-compute smallest divisor of all numbers
SieveOfEratosthenes();
$arr = array(10, 15, 7, 25, 9, 35);
$size = count($arr);
echo largestGCDSubsequence($arr, $size);
// This code is contributed by mits
?>
Javascript
<script>
// Efficient Javascript program to find length of
// the largest subsequence with GCD greater
// than 1.
let MAX = 100001;
// prime[] for storing smallest prime divisor
// of element count[] for storing the number
// of times a particular divisor occurs
// in a subsequence
let prime = new Array(MAX + 1);
let countdiv = new Array(MAX + 1);
for(let i=0;i<MAX+1;i++)
{
prime[i]=0;
countdiv[i]=0;
}
// Simple sieve to find smallest prime
// factors of numbers smaller than MAX
function SieveOfEratosthenes()
{
for (let i = 2; i * i <= MAX; ++i)
{
if (prime[i] == 0)
for (let j = i * 2; j <= MAX; j += i)
prime[j] = i;
}
// Prime number will have same divisor
for (let i = 1; i < MAX; ++i)
if (prime[i] == 0)
prime[i] = i;
}
// Returns length of the largest subsequence
// with GCD more than 1.
function largestGCDSubsequence(arr,n)
{
let ans = 0;
for (let i = 0; i < n; ++i)
{
let element = arr[i];
// Fetch total unique prime divisor of element
while (element > 1)
{
let div = prime[element];
// Increment count[] of Every unique divisor
// we get till now
++countdiv[div];
// Find maximum frequency of divisor
ans = Math.max(ans, countdiv[div]);
while (element % div == 0)
element /= div;
}
}
return ans;
}
// Driver code
// Pre-compute smallest divisor of all numbers
SieveOfEratosthenes();
let arr=[10, 15, 7, 25, 9, 35];
let size = arr.length;
document.write(largestGCDSubsequence(arr, size));
// This code is contributed by unknown2108
</script>
Producción:
4
Complejidad de tiempo: O( n*log(max(arr[i])) ) + MAX*log(log(MAX))
Espacio auxiliar: O(MAX) Shubham Bansal
contribuye con este artículo . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA