Largest subsequence having GCD greater than 1 | Efficient Python3 program to find length of the largest subsequence with GCD greater than 1. ; prime [ ] for storing smallest prime divisor of element count [ ] for storing the number of times a particular divisor occurs in a subsequence ; Simple sieve to find smallest prime factors of numbers smaller than MAX ; Prime number will have same divisor ; Returns length of the largest subsequence with GCD more than 1. ; Fetch total unique prime divisor of element ; Increment count [ ] of Every unique divisor we get till now ; Find maximum frequency of divisor ; Pre - compute smallest divisor of all numbers
import math as mt NEW_LINE MAX = 100001 NEW_LINE prime = [ 0 for i in range ( MAX + 1 ) ] NEW_LINE countdiv = [ 0 for i in range ( MAX + 1 ) ] NEW_LINE def SieveOfEratosthenes ( ) : NEW_LINE INDENT for i in range ( 2 , mt . ceil ( mt . sqrt ( MAX + 1 ) ) ) : NEW_LINE INDENT if ( prime [ i ] == 0 ) : NEW_LINE INDENT for j in range ( i * 2 , MAX + 1 , i ) : NEW_LINE INDENT prime [ j ] = i NEW_LINE DEDENT DEDENT DEDENT for i in range ( 1 , MAX ) : NEW_LINE INDENT if ( prime [ i ] == 0 ) : NEW_LINE INDENT prime [ i ] = i NEW_LINE DEDENT DEDENT DEDENT def largestGCDSubsequence ( arr , n ) : NEW_LINE INDENT ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT element = arr [ i ] NEW_LINE while ( element > 1 ) : NEW_LINE INDENT div = prime [ element ] NEW_LINE countdiv [ div ] += 1 NEW_LINE ans = max ( ans , countdiv [ div ] ) NEW_LINE while ( element % div == 0 ) : NEW_LINE INDENT element = element // div NEW_LINE DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT SieveOfEratosthenes ( ) NEW_LINE arr = [ 10 , 15 , 7 , 25 , 9 , 35 ] NEW_LINE size = len ( arr ) NEW_LINE print ( largestGCDSubsequence ( arr , size ) ) NEW_LINE