### PROBLEM LINK:

**Author:** Denis Anishchenko

**Tester:** Hasan Jaddouh

**Editorialist:** Sarv Shakti Singh

**Difficulty:** Easy

**Prerequisites:** Basic maths, gcd

**Problem:** Given an array of length `N`

and a number `K`

, you are allowed to perform as many operations. In each operation, you can divide any element in the array with a positive number less than or equal to ‘K’. Determine if it possible to modify the array by applying as many operations in such a way that the GCD of the resulting array’s elements is 1.

**Explanation:** It is easy to see that the answer is `NO`

if there exists a positive prime number greater than `K`

that divides each element of the array. So, the answer is `YES`

if the largest prime factor of the GCD of the array is less than or equal to `K`

.

Once you have the GCD of the array, all that remains is to check if there exists a prime factor of the GCD that is greater than `K`

. It could be done by this function:

```
bool check(int GCD, int K){
int max_prime = 1;
for(int i = 2; i <= sqrt(GCD); i++){ //find maximum of all the prime factors till sqrt
while(GCD % i == 0){
GCD /= i;
max_prime = max(max_prime, i);
}
}
max_prime = max(max_prime, GCD); //either GCD is reduced to 1 or a prime factor
//greater than sqrt(GCD)
if(max_prime <= K)
return true;
else
return false;
}
```

We have O(\sqrt{M} + n + \log{M}) solution per testcase, where M - is maximal number, O(\sqrt{M}) to factorize G and O(n + \log{M}) to calculate gcd of all numbers). It’s good exercise to think why counting of gcd of all numbers takes O(n + \log{M})).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.