Here is one problem idea that have. I have tried to make the problem statement as clear as possible but still let me know if it is not.
Given an array of size N ( N<=10^5 ) ( all elements are less than or equal to 300 and greater than 1) we need to find the length of the longest subsequence which follows the following property :
Let x… x[n] be a subsequence , let p,p…p[m] be prime numbers which divide atleast one of the numbers in x,…x[n] . Now for each p from 1 to m lets do the following,Let productX ( a variable ) =1 :
If p[i] divides only 1 number in 1…n then find the largest power of this primes which divides that number and multiply it to productX
If p[i] divides more than 1 number then find the largest power of this prime which divides each of the numbers. Now you have n numbers like y,y…y[n] ( y[i] is basically the largest power of prime p which divides x[i]).Among those numbers select the smallest and the largest number and multiply it to productX ( Selected numbers must be greater than 1 ).
Now if productX == Product of numbers in that subsequence then it is a valid subsequence .
Example 1) 2 2 4 3 In this case answer is 3 ( Subarray is 2 2 3 or 2 4 3 ). 2 2 4 3 wont be valid because product of numbers is 48 and productX is 2** 4 **3=24 .
I thought of solving this using Max flow .