Back From Summer '19 P6: Composite Zeyu

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.75s
Memory limit: 128M

Problem types

Zealous Zeyu is looking for a brand new set of arms today!

There are N arms currently on sale. The i^\text{th} arm has a length of a_i zeyumeters from end to end. For legal and aesthetic reasons, the store refuses to sell you two of the same arm (i.e. two of arm i).

Zeyu is looking to replace k of his arms. He prefers sets of arms where the product of its arm lengths contains the minimal number of unique prime factors. He likes to be as prime as possible 😎.

What is the minimal number of unique prime factors of such a set? Zeyu needs to know this in order to make the best possible purchase.

Input Specification

The first line will contain one integer, N (1 \le N \le 10^5).

The second line will contain N integers, a_i (2 \le a_i \le 10^9), the lengths of the arms.

Read carefully: It is guaranteed that a_i's prime factors will have a value of less than or equal to 75. In other words, if a_i = b_1^{m_1} \times b_2^{m_2} \times \dots \times b_k^{m_k} where b_j is a unique prime, then 2 \le b_j \le 75.

Output Specification

Output N space separated integers, the k^\text{th} (1 \le k \le N) integer representing the minimum number of unique prime factors for the product of k arm lengths in a set.


Subtask 1 [5%]

N \le 15

Subtask 2 [25%]

N \le 100

Subtask 3 [70%]

No additional constraints.

Sample Input 1

2 20 10 15

Sample Output 1

1 2 2 3

Sample Input 2

7 153 10

Sample Output 2

1 3 5


There are no comments at the moment.