# No of subsets of a given array such that their product is in the form of p1*p2*p3 [closed]

Given an array $$\A\$$ of size $$\n\$$. You have to find the number of subsets such that their product is in the form of $$\p_1 \times p_2 \times p_3 \dots\$$ where $$\p_1, p_2, p_3, \dots\$$ are prime numbers. No prime number should appear more than once, i.e. the product is "squarefree".

Example: Lets pick an array $$\A\$$ of size $$\5\$$. $$\A[5] = \{2, 3, 15, 55, 21\}\$$ The subsets in our answers should be $$\\{2,3\}, \{2, 15\}, \{2, 55\}, \{2, 21\}, \{2, 3, 55\}, \{2, 55, 21\}, \{3, 55\}, \{55, 21\}\$$. Lets take $$\\{2, 3, 55\}\$$ The product will be $$\2 \times 3 \times 55 = 2 \times 3 \times 5 \times 11\$$. Thus all prime numbers with power of 1. We can't take for example $$\\{3, 15\}\$$ because $$\3 \times 15 = 3^2 \times 5\$$. Condition not satisfied. Therefore our answer should be number of subsets i.e. here 8.

Constraints: $$\2\leq A_i<10^9\$$, $$\1\leq n<10^5\$$

• Welcome to CGCC. Please read how to ask - your question right now is missing several details; the wording could be more clear but I understood the body of the challenge, but it is missing a scoring criterion. I would advise drafting your challenge in the Sandbox before posting in the future; it's helpful for getting feedback first. Jun 25, 2021 at 5:48
• Note that the term you are likely looking for, to describe the products, is "squarefree" - that is, 42 is squarefree because there is no square factor except 1, while 45 is not squarefree because 9 is a factor, and 9 is square. Jun 25, 2021 at 6:23
• Looks like the question simply asks for coprime subsets of A. Jun 25, 2021 at 6:32
• @pajonk That would be different if input array contains numbers already multiple of square numbers. For example, $A\left[3\right]=\left\{2,3,4\right\}$.
– tsh
Jun 25, 2021 at 7:29
• What is the source of this question? It really looks like it was copied from a programming site.
– xnor
Jun 25, 2021 at 10:19

# Vyxals, 16 bytes
ṗ'L1>;ƛΠǐ:UL\$L"≈