### PROBLEM LINK:

**Author:** Roman Kachur

**Tester:** Kevin Charles Atienza

**Editorialist:** Vaibhav Tulsyan

### DIFFICULTY:

Easy-medium

### PREREQUISITES:

Prime-factorization, GCD, Sieve of Eratosthenes, Dynamic Programming

### PROBLEM:

Given a sequence of integers, finding its longest sub-sequence such that the *GCD* of the every consecutive integer is greater than 1.

### QUICK EXPLANATION:

Pre-compute the smallest prime-factor of all integers from 1 to 10^7 using the Sieve of Eratosthenes.

Use dynamic programming to store the maximum length of the required sub-sequence such that consecutive integers have common prime-factors.

f(i, P) stores the maximum length of the sub-sequence uptil index i such that the last-used prime factor is P.

Note: In the DP table, we only need to maintain the max length for each prime uptil now - without storing the information for each and every index.

### EXPLANATION:

**Subtask 1:**

For this subtask, the constraint on the no. of integers (N) in the array is: 1 \le N \le 10^3.

For each index i, we can find number of indexes j (j \lt i) such that gcd(a_i, a_j) > 1. Let’s call this value V_i.

Our goal is to maximize V_i over all i from 1 to N.

The complexity of this solution is: O(N^2 * log(max(a_i))).

This solution would fetch 30 points.

**Subtask 2:**

When we say that we want to find the longest sub-sequence that had gcd > 1, it is equivalent to saying we want to find the longest sub-sequence

which has a *common prime-factor*. This is true owing to the nature of the gcd function.

- Approach

For each index i in the given array, we can store the set S of prime factors of all integers we have seen upto this index.

For each of these prime factors P, we can maintain a value count_{P} - the number of integers that have P as a prime factor.

Our final answer would be: max(count_{P}), across all P present in S after going through the entire array.

- Implementation

- We will need to prime-factorize each integer in the array.

We first use sieve to find the smallest prime factor of all integers in range [1…10^7].

Pseudo-code for pre-computing smallest prime factors using sieve:

smallest_prime_factor = [1 for all ints uptil 10^7] # initialize

for i in [2…10^7]:

if smallest_prime_factor* == 1:

for j in [i…10^7]:

smallest_prime_factor[j] = i

j += i

Pseudo-code for prime-factorization of a number:

prime_factors = set()

while number != 1:

prime_factors.add(smallest_prime_factor[number])

number /= smallest_prime_factor[number]

Now, we can use dynamic programming to store the *maximum* possible sub-sequence length that ends at index i, such that a_i contains P as a prime factor.

Let the prime factors of a_i be p_1, p_2, p_3, ... , p_K.

For each p_j, let’s say the maximum possible sub-sequence length such that the previous selected number had a common prime factor was l_j.

We choose the maximum length M equal to max(l_j) (1 \le j \le K). We update dp(p_j) with the value M.

While performing updates, we maintain a global maximum - the maximum M calculated uptil now.

- Complexity

- Pre-computation using sieve: O(X*log(log(X))), where X = 10^7.
- Computation of max length sub-sequence: O(N * log_2(Y)), where Y is the number in the array with maximum no. of prime factors.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.