Tìm số có nhiều ước dương nhất trong mảng 1 chiều c++

Lý thuyết

`\text{Cách 1: Chạy duyệt trâu}`

`\text{ĐPT: O(n*sqrt(x))}`

`\text{Cách 2: Sàng}`

`\text{O(n + max(x) log log max(x))}`

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int cnt[N];

void sieve() {
    for (int i = 1; i < N; ++i) {
        for (int j = i; j < N; j += i) {
            ++cnt[j];
        }
    }
}

int trau(const vector<int>& a) {
    int max = 0;
    int n = a[0];
    
    for (int num : a) {
         int d = cnt[num];
         if (d > max) {
           max = d;
             n = num;
        }
    }
    
    return n;
}

int main() {
    sieve();
    vector<int> a = {10, 24, 18, 30, 16, 12};
    int res = trau(a);
    cout << res << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int Dem(int n)
{
  int k = sqrt(n), s = 0;
  for (int i = 1; i <= k; i ++)
  {
    if (n % i == 0) s += 2;
  }
  if (k * k == n) return s - 1;
  else return s;
}
int main() 
{
  int n, Mx = -1000000; cin >> n;
  int a[n];
  for (int i = 0; i < n; i ++)
  {
    cin >> a[i];
    if (Dem(a[i]) > Mx) Mx = a[i];
  }
  cout << Mx;
}