You are not logged in. Please login at to post your questions!


KIRLAB - Editorial





Author: Roman Kachur

Tester: Kevin Charles Atienza

Editorialist: Vaibhav Tulsyan




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


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


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.


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[i] == 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.


Setter's solution can be found here.

Tester's solution can be found here.

Editorialist's solution can be found here.

This question is marked "community wiki".

asked 13 Mar '17, 20:33

wittyceaser's gravatar image

accept rate: 16%

edited 10 Aug '18, 16:00

admin's gravatar image

0★admin ♦♦

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 13 Mar '17, 20:33

question was seen: 143 times

last updated: 10 Aug '18, 16:00