<style>
html, body, .ui-content {
background-image: url(https://truth.bahamut.com.tw/s01/201508/7f0e4bd0e01135c9df434733e0d1544a.JPG);
background-color: #333;
color: #DDD;
}
</style>

###### tags: `Meowmeow Online Judge`

# Common Divisors
## Description
You are given an array of $n$ positive integers. Your task is to find two integers such that their greatest common divisor is as large as possible.

## Input
The first line has an integer $n$: the size of the array.

The second line has $n$ integers $x_1$, $x_2$, $\cdots$, $x_n$: the contents of the array.
$2≤n≤2⋅10^5$
$1≤x^i≤10^6$

## Output
Print the maximum greatest common divisor.

## 解題思路
除數由大到小去確認自己的倍數在不在input裡面，直到找到兩個數可以整除它為止
### 時間複雜度
$O(\frac n 1 + \frac n 2 + \frac n 3 + \cdots + \frac n n)
= O(n\ lg\ n)$

## Code

#include <iostream>
#include <vector>

int main() {
    int size, content;
    std::cin >> size;
    std::vector<int> exist(1000001, 0);
    for (int i = 0; i < size; i++) {
        std::cin >> content;
        exist[content]++;
    }

    for (int divisor = 1000000; divisor > 0; divisor--) {
        int count = 0;
        for (int i = 1; i * divisor <= 1000000; i++) count += exist[i * divisor];
        if (count >= 2) {
            std::cout << divisor << std::endl;
            return 0;
        }
    }
    std::cout << "something wrong" << std::endl;
    return 0;
}