310371: CF1823C. Strongly Composite
Description
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.
InputEach 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$.
OutputFor each test case, print the size $k$ of array $b$, or $0$, if there is no array $b$ satisfying the conditions.
ExampleInput8 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 39Output
1 1 0 2 2 3 4 15Note
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.
Input
题意翻译
质数是指大于 $1$ 且仅有 $2$ 个约数的数，例如 $7$ 的约数只有 $1$ 和 $7$，所以 $7$ 是质数。而合数则是大于 $1$ 且具有超过 $2$ 个约数的数。 注意 $1$ 既不是质数也不是合数。 对于一个合数，它会有许多的约数，它的约数中有些是质数，有些是合数，如果该合数的约数中质数的个数小于等于合数的个数，那么我们称这个合数为强合数。 例如，$12$ 有 $6$ 个约数 $\{1,2,3,4,6,12\}$，其中 $2$ 和 $3$ 是质数，$4$、$6$、$12$ 是合数，所以 $12$ 的约数中有 $2$ 个质数，$3$ 个合数，质数的个数小于合数的个数，所以 $12$ 是强合数。其他的强合数还有 $4$、$8$、$9$、$16$ 等等。 另外，$15$ 有 $4$ 个约数 $\{1,3,5,15\}$，其中 $3$、$5$ 是质数，$15$ 是合数，所以 $15$ 的约数中有 $2$ 个质数，$1$ 个合数，所以 $15$ 不是强合数。其他的不是强合数的数还有 $2$、$3$、$5$、$6$、$7$、$10$ 等等。 给你一个长度为 $n$ 的整数数组 $a_1,a_2,\dots,a_n(a_i>0)$，请你构造一个满足下列条件的数组 $b_1,b_2,\dots,b_k$。 - $a_1\times a_2\times\dots\times a_n=b_1\times b_2\times\dots\times b_k$； - $b$ 数组中的所有数都是强合数; - $b$ 数组的大小 $k$ 在满足上述条件的前提下要尽可能的大。 如果存在这样的数组 $b$，请找到的这样的数组 $b$ 并输出 $b$ 数组大小 $k$，如果不存在输出 $0$ 即可。Output
一个质数是一个大于1的整数，它恰好有两个除数。例如，7是一个质数，因为它有两个除数{1, 7}。一个合数是一个大于1的整数，它有超过两个不同的除数。注意，整数1既不是质数也不是合数。
如果一个合数v的质数除数的数量小于或等于合数除数的数量，那么称v为强合数。例如，数字12有6个除数：{1, 2, 3, 4, 6, 12}，其中两个除数2和3是质数，而三个除数4、6和12是合数。所以，12是一个强合数。其他强合数的例子有4、8、9、16等等。
另一方面，15的除数是{1, 3, 5, 15}：3和5是质数，15是合数。所以，15不是一个强合数。其他例子有：2、3、5、6、7、10等等。
给定n个整数a1, a2, …, an (ai > 1)。您必须构建一个数组b1, b2, …, bk，使得以下条件得到满足：
1. 数组a的所有元素之积等于数组b的所有元素之积：a1 ⋅ a2 ⋅ … ⋅ an = b1 ⋅ b2 ⋅ … ⋅ bk；
2. 数组b的所有元素都是大于1的整数且为强合数；
3. 数组b的大小k是尽可能大的。
找到数组b的大小k，或者报告没有满足条件的数组b。
输入数据格式：
每个测试包含多个测试用例。第一行包含测试用例的数量t (1 ≤ t ≤ 1000)。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n (1 ≤ n ≤ 1000) —— 数组a的大小。
第二行包含n个整数a1, a2, …, an (2 ≤ ai ≤ 10^7) —— 数组a本身。
保证所有测试用例中n的总和不超过1000。
输出数据格式：
对于每个测试用例，打印数组b的大小k，如果没有满足条件的数组b，则打印0。
示例：
输入：
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
0
2
2
3
4
15
注意：
在第一个测试用例中，我们可以得到数组b = [18]：a1 ⋅ a2 = 18 = b1；18是一个强合数。
在第二个测试用例中，我们可以得到数组b = [60]：a1 ⋅ a2 ⋅ a3 = 60 = b1；60是一个强合数。
在第三个测试用例中，没有满足条件的数组b。
在第四个测试用例中，我们可以得到数组b = [4, 105]：a1 ⋅ a2 ⋅ a3 = 420 = b1 ⋅ b2；4和105都是强合数。题目大意： 一个质数是一个大于1的整数，它恰好有两个除数。例如，7是一个质数，因为它有两个除数{1, 7}。一个合数是一个大于1的整数，它有超过两个不同的除数。注意，整数1既不是质数也不是合数。 如果一个合数v的质数除数的数量小于或等于合数除数的数量，那么称v为强合数。例如，数字12有6个除数：{1, 2, 3, 4, 6, 12}，其中两个除数2和3是质数，而三个除数4、6和12是合数。所以，12是一个强合数。其他强合数的例子有4、8、9、16等等。 另一方面，15的除数是{1, 3, 5, 15}：3和5是质数，15是合数。所以，15不是一个强合数。其他例子有：2、3、5、6、7、10等等。 给定n个整数a1, a2, …, an (ai > 1)。您必须构建一个数组b1, b2, …, bk，使得以下条件得到满足： 1. 数组a的所有元素之积等于数组b的所有元素之积：a1 ⋅ a2 ⋅ … ⋅ an = b1 ⋅ b2 ⋅ … ⋅ bk； 2. 数组b的所有元素都是大于1的整数且为强合数； 3. 数组b的大小k是尽可能大的。 找到数组b的大小k，或者报告没有满足条件的数组b。 输入数据格式： 每个测试包含多个测试用例。第一行包含测试用例的数量t (1 ≤ t ≤ 1000)。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n (1 ≤ n ≤ 1000) —— 数组a的大小。 第二行包含n个整数a1, a2, …, an (2 ≤ ai ≤ 10^7) —— 数组a本身。 保证所有测试用例中n的总和不超过1000。 输出数据格式： 对于每个测试用例，打印数组b的大小k，如果没有满足条件的数组b，则打印0。 示例： 输入： 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 0 2 2 3 4 15 注意： 在第一个测试用例中，我们可以得到数组b = [18]：a1 ⋅ a2 = 18 = b1；18是一个强合数。 在第二个测试用例中，我们可以得到数组b = [60]：a1 ⋅ a2 ⋅ a3 = 60 = b1；60是一个强合数。 在第三个测试用例中，没有满足条件的数组b。 在第四个测试用例中，我们可以得到数组b = [4, 105]：a1 ⋅ a2 ⋅ a3 = 420 = b1 ⋅ b2；4和105都是强合数。