A15925. Strongly Composite
编程题
普及/提高-
知识点
题目描述
A prime number is an integer greater than $1$ , which has exactly two divisors. For example, $7$ is a prime, since it has two divisors $\{1, 7\}$ . A composite number is an integer greater than $1$ , which has more than two different divisors.
Note that the integer $1$ is neither prime nor composite.
Let's look at some composite number $v$ . It has several divisors: some divisors are prime, others are composite themselves. If the number of prime divisors of $v$ is less or equal to the number of composite divisors, let's name $v$ as strongly composite.
For example, number $12$ has $6$ divisors: $\{1, 2, 3, 4, 6, 12\}$ , two divisors $2$ and $3$ are prime, while three divisors $4$ , $6$ and $12$ are composite. So, $12$ is strongly composite. Other examples of strongly composite numbers are $4$ , $8$ , $9$ , $16$ and so on.
On the other side, divisors of $15$ are $\{1, 3, 5, 15\}$ : $3$ and $5$ are prime, $15$ is composite. So, $15$ is not a strongly composite. Other examples are: $2$ , $3$ , $5$ , $6$ , $7$ , $10$ and so on.
You are given $n$ integers $a_1, a_2, \dots, a_n$ ( $a_i > 1$ ). You have to build an array $b_1, b_2, \dots, b_k$ such that following conditions are satisfied:
- Product of all elements of array $a$ is equal to product of all elements of array $b$ : $a_1 \cdot a_2 \cdot \ldots \cdot a_n = b_1 \cdot b_2 \cdot \ldots \cdot b_k$ ;
- All elements of array $b$ are integers greater than $1$ and strongly composite;
- The size $k$ of array $b$ is the maximum possible.
Find the size $k$ of array $b$ , or report, that there is no array $b$ satisfying the conditions.
Note that the integer $1$ is neither prime nor composite.
Let's look at some composite number $v$ . It has several divisors: some divisors are prime, others are composite themselves. If the number of prime divisors of $v$ is less or equal to the number of composite divisors, let's name $v$ as strongly composite.
For example, number $12$ has $6$ divisors: $\{1, 2, 3, 4, 6, 12\}$ , two divisors $2$ and $3$ are prime, while three divisors $4$ , $6$ and $12$ are composite. So, $12$ is strongly composite. Other examples of strongly composite numbers are $4$ , $8$ , $9$ , $16$ and so on.
On the other side, divisors of $15$ are $\{1, 3, 5, 15\}$ : $3$ and $5$ are prime, $15$ is composite. So, $15$ is not a strongly composite. Other examples are: $2$ , $3$ , $5$ , $6$ , $7$ , $10$ and so on.
You are given $n$ integers $a_1, a_2, \dots, a_n$ ( $a_i > 1$ ). You have to build an array $b_1, b_2, \dots, b_k$ such that following conditions are satisfied:
- Product of all elements of array $a$ is equal to product of all elements of array $b$ : $a_1 \cdot a_2 \cdot \ldots \cdot a_n = b_1 \cdot b_2 \cdot \ldots \cdot b_k$ ;
- All elements of array $b$ are integers greater than $1$ and strongly composite;
- The size $k$ of array $b$ is the maximum possible.
Find the size $k$ of array $b$ , or report, that there is no array $b$ satisfying the conditions.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 1000$ ). The description of the test cases follows.
The first line of each test case contains one integer $n$ ( $1 \le n \le 1000$ ) — the size of the array $a$ .
The second line of each test case contains $n$ integer $a_1, a_2, \dots a_n$ ( $2 \le a_i \le 10^7$ ) — the array $a$ itself.
It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$ .
The first line of each test case contains one integer $n$ ( $1 \le n \le 1000$ ) — the size of the array $a$ .
The second line of each test case contains $n$ integer $a_1, a_2, \dots a_n$ ( $2 \le a_i \le 10^7$ ) — the array $a$ itself.
It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$ .
输出格式
For each test case, print the size $k$ of array $b$ , or $0$ , if there is no array $b$ satisfying the conditions.
输入输出样例
输入 #1
8 2 3 6 3 3 4 5 2 2 3 3 3 10 14 2 25 30 1 1080 9 3 3 3 5 5 5 7 7 7 20 12 15 2 2 2 2 2 3 3 3 17 21 21 21 30 6 6 33 31 39
输出 #1
1 1 0 2 2 3 4 15
说明/提示
In the first test case, we can get array $b = [18]$ : $a_1 \cdot a_2 = 18 = b_1$ ; $18$ is strongly composite number.
In the second test case, we can get array $b = [60]$ : $a_1 \cdot a_2 \cdot a_3 = 60 = b_1$ ; $60$ is strongly composite number.
In the third test case, there is no array $b$ satisfying the conditions.
In the fourth test case, we can get array $b = [4, 105]$ : $a_1 \cdot a_2 \cdot a_3 = 420 = b_1 \cdot b_2$ ; $4$ and $105$ are strongly composite numbers.
In the second test case, we can get array $b = [60]$ : $a_1 \cdot a_2 \cdot a_3 = 60 = b_1$ ; $60$ is strongly composite number.
In the third test case, there is no array $b$ satisfying the conditions.
In the fourth test case, we can get array $b = [4, 105]$ : $a_1 \cdot a_2 \cdot a_3 = 420 = b_1 \cdot b_2$ ; $4$ and $105$ are strongly composite numbers.