Skip to content
Related Articles

Related Articles

Largest subsequence having GCD greater than 1

View Discussion
Improve Article
Save Article
  • Difficulty Level : Medium
  • Last Updated : 11 Aug, 2021
View Discussion
Improve Article
Save Article

Given an array, arr[], find the largest subsequence such that GCD of all those subsequences are greater than 1. 
Examples: 
 

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

 

 

Naive Approach(Method 1)

Simple approach is to generate all the subsequence one by one and then find the GCD of all such generated set. Problem of this approach is that it grows exponentially in 2N
 

Iterative Approach(Method 2)

If we observe then we will found that to make gcd greater than 1, all such elements must contain common factor greater than 1 which evenly divides all these values. So in order to get that factor we will iterate from 2 to Maximum element of array and then check for divisibility. 
 

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>
Output: 
 
3
Time Complexity: O(n * max(arr[i])) where n is size of array. 
Auxiliary Space: O(1)
 
Best Approach(Method 3)
An efficient approach is to use prime factorization method with the help of Sieve of Eratosthenes. First of all we will find the smallest prime divisor of all elements by pre-computed sieve. After that we will mark all the prime divisor of every element of arr[] by factorizing it with the help of pre-computed prime[] array. 
Now we have all the marked primes occurring in all the array elements. The last step is to find the maximum count of all such prime factors. 
 
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>
Output: 
 
 4
Time complexity: O( n*log(max(arr[i])) ) + MAX*log(log(MAX)) 
Auxiliary space: O(MAX)
This article is contributed by Shubham Bansal. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
 

My Personal Notes
arrow_drop_up
Previous
Pascal's Triangle
Next

Find x and y satisfying ax + by = n
Recommended Articles
Page :
Find N distinct integers with GCD of sequence as 1 and GCD of each pair greater than 1
07, Dec 21
Smallest subsequence having GCD equal to GCD of given array
20, Oct 20
Pair of integers having least GCD among all given pairs having GCD exceeding K
16, Sep 20
Split N natural numbers into two sets having GCD of their sums greater than 1
06, May 20
Smallest subarray of size greater than K with sum greater than a given value
27, Sep 20
Largest integer upto N having greatest prime factor greater than its square root
05, Oct 21
Largest number with maximum trailing nines which is less than N and greater than N-D
20, Aug 18
Largest number less than N with digit sum greater than the digit sum of N
04, Dec 18
Count all possible values of K less than Y such that GCD(X, Y) = GCD(X+K, Y)
13, Jan 21
Maximum count of pairs in Array with GCD greater than 1 by reordering given Array
19, Jan 22
Check if GCD of Array can be made greater than 1 by replacing pairs with their products
29, Jan 22
Find N - 1 pairs from given array such that GCD of all pair-sums is greater than 1
31, Jan 22
Find minimum sum Pair whose GCD is greater than 1
19, Apr 22
Smallest divisor D of N such that gcd(D, M) is greater than 1
05, Mar 19
GCD of array is greater than one
17, Nov 17
Longest subarray with GCD greater than 1
05, Aug 21
Minimum length of subsequence having unit GCD
24, Aug 20
Longest subsequence having maximum GCD between any pair of distinct elements
27, Oct 20
Length of longest subsequence such that prefix sum at every element remains greater than zero
19, Oct 21
Largest number not greater than N which can become prime after rearranging its digits
18, Apr 19
Largest even digit number not greater than N
21, Mar 18
Largest number not greater than N all the digits of which are odd
18, Nov 18
Count pairs having bitwise XOR greater than K from a given array
25, Oct 20
Smallest number greater than or equal to N having sum of digits not exceeding S
05, Nov 20
Article Contributed By :
https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
Vote for difficulty
Current difficulty :
Medium





Improved By :
Article Tags :
Practice Tags :
Report Issue

We use cookies to ensure you have the best browsing experience on our website. By using our site, you
acknowledge that you have read and understood our
Cookie Policy &
        Privacy Policy

Lightbox

Start Your Coding Journey Now!