What's wrong in my solution for KIRLAB problem, getting WA?

general
1

Problem Page : KIRLAB

My solution : Solution WA

It is asking to find out the longest subsequence in array such that every adjacent pair of the subsequence has GCD>1, or we can say every adjacent pair shares some common prime factor.

Suppose We are given array A[ ].
I made an array B[ ] of 10^7 size and initialized with all zeroes.
Then I traverse the given array A[ ], and for each element A[i], I increment B[j] for all prime factors j of A[i] and choose the max of the updated $B[j]$s and then update all these $B[j]$s with this chosen max value. In this way, max of array B[] now tells the max length of subsequence found till now.

This solution is giving WA. Please tell me what is wrong in my solution.

Thanks

2

You’re doing the prime factorisation wrong, for each number, you’re only considering those primes whose square is less than or equal to the number, take 20 for example, try printing the prime_factors vector in your program, it gives 2 as the only prime factor. In a test case like this: 1 5 10 20 15 30 40 Although the answer is supposed to be 5, your code gives 4 as the answer.

3

Wow, Hermanth_1 u are good, So is that clarifies you rahul1995?