หาตัวเลขที่หารสมาชิกในอาร์เรย์ได้มากที่สุดใน C++

โจทย์

ได้รับอาร์เรย์ arr[] ทางเราต้อง หาตัวเลขที่หารสมาชิกในอาร์เรย์ได้มากที่สุด (ถ้ามีหลายตัว ให้ตัวเล็กกว่า)

ตัวอย่าง

Input: arr[] = {4, 5, 6, 7, 8}

Output: 2

อธิบาย: 2 หาร 4, 6, 8 ได้ (3 ตัว)

แนวทางแก้ปัญหา

ใช้ Sieve of Eratosthenes หาตัวประกอบเฉพาะ (Prime Factors) ของทุกตัวในอาร์เรย์ นับความถี่ของแต่ละเฉพาะ ตัวที่มีความถี่มากที่สุด (และเล็กที่สุดถ้าเท่ากัน) คือคำตอบ

โปรแกรมตัวอย่าง

#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 /= 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 x : p) factorFreq[x]++;
    }
    int cnt = 0, ans = 1e7;
    for (auto itr : factorFreq) {
        if (itr.second >= cnt) {
            cnt = itr.second;
            ans = min(ans, itr.first);
        }
    }
    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;
}

ผลลัพธ์

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