Tìm số nguyên chia hết cho nhiều phần tử mảng nhất trong C++

Cho mảng arr[] n số nguyên. Nhiệm vụ: tìm số nguyên chia hết cho nhiều phần tử mảng nhất.

Mô tả: Tìm số p chia hết cho nhiều phần tử mảng nhất. Nếu nhiều số thỏa mãn, lấy số nhỏ hơn.

Ví dụ:

Đầu vào: arr[] = {4, 5, 6, 7, 8}

Đầu ra: 2

Giải thích:

Số 2 chia hết cho {4, 6, 8}.

Phương pháp giải

Cách đơn giản: duyệt mảng, với mỗi phần tử thử chia cho các số từ 1 đến max. Đếm tần suất.

Cách tối ưu: dùng sàng Eratosthenes tìm ước số nguyên tố. Đếm tần suất xuất hiện của từng ước nguyên tố. Trả về ước có tần suất cao nhất (nhỏ nhất nếu bằng nhau).

Chương trình minh họa

Ví dụ

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

#define MAXN 100001
int primes[MAXN];

void findPrimeSieve() {
    primes[1] = 1;
    for (int i = 2; i < MAXN; i++)
        primes[i] = i;
    for (int i = 4; i < MAXN; i += 2)
        primes[i] = 2;
    for (int i = 3; i * i < MAXN; i++) {
        if (primes[i] == i) {
            for (int j = i * i; j < MAXN; j += i)
                if (primes[j] == j)
                    primes[j] = i;
        }
    }
}

vector<int> findFactors(int num) {
    vector<int> factors;
    while (num != 1) {
        int temp = primes[num];
        factors.push_back(temp);
        while (num % temp == 0)
            num = num / temp;
    }
    return factors;
}

int findmaxDivElement(int arr[], int n) {
    findPrimeSieve();
    map<int, int> factorFreq;
    for (int i = 0; i < n; ++i) {
        vector<int> p = findFactors(arr[i]);
        for (int i = 0; i < p.size(); i++)
            factorFreq[p[i]]++;
    }
    int cnt = 0, ans = 1e+7;
    for (auto itr : factorFreq) {
        if (itr.second >= cnt) {
            cnt = itr.second;
            ans > itr.first ? ans = itr.first : ans = ans;
        }
    }
    return ans;
}

int main() {
    int arr[] = { 4, 5, 6, 7, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The number that divides the maximum elements of the array is " << findmaxDivElement(arr, n);
    return 0;
}

Kết quả

The number that divides the maximum elements of the array is 2