### PROBLEM LINK:

**Author:** Rahim Mammadi

**Primary Tester:** Amir Reza PoorAkhavan

**Editorialist:** Hussain Kara Fallah

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

Sieve of Eratosthenes

### PROBLEM:

Given an array of **N** integers (all integers are up to 10^5). Let’s suppose we have taken a non-empty subset of this array. The magical value of this subset is **(Number of distinct prime numbers that divides every number of the subset * the size of this subset)**. Find the subset with the maximum magical number and output this number.

### EXPLANATION:

First of all, **Number of distinct prime numbers that divide every number of the subset** is equivalent to **the number of prime factors of GCD of this subset**.

Let’s try all possible **GCDs**. How’s that possible?

If you don’t know Sieve then stop reading and take a look at this link. After that, try to figure out the solution yourself.

What’s the optimal subset for a certain **GCD** (let’s say **K**) ?. Clearly, we can take a subset of all of its multiples in the array. Please note that the **GCD** of this subset would be **K** or one of its multiples, but that doesn’t affect the answer (Why?). Because we will have the same subset when handling this (multiple of K) which is the real GCD and since it’s a multiple of **K**, it has at least the same number of prime factors hence, the answer will be updated for sure. So we can safely assume the the **GCD** is equal to **K** with no problems.

How to loop over the multiples of a number **K**?

```
for(int i = K ; i < MX ; i += K){
tot += cnt[i]; //you can do anything
}
```

So our code looks like this:

```
for(int G = 2 ; G < MX ; G++){ //loop for every possible GCD
int subsetSize = 0;
for(int i = G ; i < MX ; i += G) // counting how many multiples there are
subsetSize += cnt[i];
}
```

The complexity of this loop is:

which is equal to:

The sum of the series:

So total complexity is MaxValue * log (MaxValue)

There is also a part left for you, which is figuring the number of prime factors. This is easy, and can be done also while doing the Sieve approach (left for you), or you can check the codes.