Hackerrank - Easy GCD

We call a sequence of  non-negative integers, , awesome if there exists some positive integer such that each element  in  (where ) is evenly divisible by . Recall that  evenly divides  if there exists some integer  such that .

Given an awesome sequence, , and a positive integer, , find and print the maximum integer, , satisfying the following conditions:

2.  is also awesome.

Input Format

The first line contains two space-separated positive integers,  (the length of sequence ) and  (the upper bound on answer ), respectively. 
The second line contains  space-separated positive integers describing the respective elements in sequence  (i.e., ).

Constraints

Output Format

Print a single, non-negative integer denoting the value of  (i.e., the maximum integer  such that  is awesome). As  is evenly divisible by any , the answer will always exist.

Sample Input 0

3 5
2 6 4

Sample Output 0

4

Explanation 0

The only common positive divisor of , , and  that is  is , and we need to find  such that . We know  because  would not evenly divide . When we look at the next possible value, , we find that this is valid because it's evenly divisible by our  value. Thus, we print .

Sample Input 1

1 5
7

Sample Output 1

0

Explanation 1

Being prime,  is the only possible value of . The only possible  such that  is  (recall that ), so we print  as our answer.

Solution:

1. #include <bits/stdc++.h>
2. using namespace std;
3.  
4. vector <int> PF;
5.  
6. void primeFactors(int n){
7.     while (n%2 == 0){
8.         PF.push_back(2);
9.         n = n/2;
10.     }
11.     for (int i = 3; i <= sqrt(n); i = i+2){
12.         while (n%i == 0){
13.             PF.push_back(i);
14.             n = n/i;
15.         }
16.     }
17.     if (n > 2)PF.push_back(n);
18. }
19.  
20. int main(){
21.     int n, k, x;
22.     scanf("%d", &n);
23.     scanf("%d", &k);
24.     int g, f = 0;
25.     for(int i = 0; i < n; i++){
26.         scanf("%d", &x);
27.         if(!f){
28.             f = 1;
29.             g = x;
30.         }
31.         g = __gcd(g, x);
32.     }
33.     if(g < 2)return 0*puts("0");
34.     primeFactors(g);
35.     int sz = PF.size();
36.     int mx = 0;
37.     for(int i = 0; i < sz; i++){
38.         int z = k/PF[i];
39.         mx = max(mx, z*PF[i]);
40.     }
41.     printf("%d\n", mx);
42.     return 0;
43. }