While solving I came up with an algorithm, but don't know the permutation and combinations to proceed further. The algorithm is as follows:

1) Input the numbers in a vector "v"

2) Make a vector "primes" consisting of the prime numbers using Sieve of Eratosthenes.

3) For every element in v, divide it by all primes smaller than it (if divisible).

4) Sort it

5) We will now have vector consisting of (1,1,1,1,2,2,2,3,3,5,5,6,6,6,7 ... types) i.e. all numbers except of perfect squares (1 will be there) Now for the part I could not solve :

6) I want to arrange this vector thus formed of length n in such a manner that no 1's appear together, no 2's appear together, no 3's appear together ...etc. For example, the given case : {1,4,2} after step 3: {1,1,2} after step 4 {1,1,2} (since already sorted) after step 5 {1,2,1} is the valid arrays.

7) I have to multiply this by a certain number but let's leave this for now.

How can I solve the part 6).. ?