ปัจจัยเฉพาะของ LCM ของสมาชิกในอาร์เรย์ใน C++

ภาพรวมปัญหา

ได้รับอาร์เรย์ที่ค่าอยู่ในช่วง 1 ≤ arr[i] ≤ 10^12 ต้องพิมพ์ปัจจัยเฉพาะทั้งหมดของ LCM (ตัวคูณร่วมน้อย) ของสมาชิกทุกตัวในอาร์เรย์

ตัวอย่าง

Input: array = {2, 5, 15}
Output: 2 3 5
Explanation: LCM = 30, ปัจจัยของ 30 = 2 × 3 × 5

วิธีแก้ปัญหา

การหา LCM ของตัวเลขขนาด 10^12 โดยตรงอาจหนักเกินไป ใช้แนวคิดว่า:

ปัจจัยเฉพาะของตัวเลขแต่ละตัว จะเป็นปัจจัยเฉพาะของ LCM ของพวกมันด้วย

ขั้นตอน:

หาจำนวนเฉพาะด้วย Sieve of Sundaram
แยกตัวประกอบเฉพาะของแต่ละสมาชิกในอาร์เรย์
เก็บปัจจัยเฉพาะที่พบในอาร์เรย์ flag (factors[])
พิมพ์ปัจจัยเฉพาะที่มี flag = 1

ตัวอย่างโค้ด C++

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

const int MAX = 1000000;
typedef long long int ll;
vector <int> primeNumbers;

void findPrimeNumbers() {
    int n = MAX;
    int nNew = (n)/2;
    bool marked[nNew + 100];
    memset(marked, false, sizeof(marked));
    int tmp = sqrt(n);
    for (int i = 1; i <= (tmp-1)/2; i++)
        for (int j = (i*(i+1))<<1; j <= nNew; j = j + 2*i + 1)
            marked[j] = true;
    primeNumbers.push_back(2);
    for (int i = 1; i <= nNew; i++)
        if (marked[i] == false)
            primeNumbers.push_back(2*i + 1);
}

void printPrimeLCM(ll arr[], int n) {
    findPrimeNumbers();
    int factors[MAX] = {0};
    for (int i = 0; i < n; i++) {
        ll copy = arr[i];
        int sqr = sqrt(copy);
        for (int j = 0; primeNumbers[j] <= sqr; j++) {
            if (copy % primeNumbers[j] == 0) {
                while (copy % primeNumbers[j] == 0)
                    copy = copy / primeNumbers[j];
                factors[primeNumbers[j]] = 1;
            }
        }
        if (copy > 1)
            factors[copy] = 1;
    }
    if (factors[2] == 1)
        cout << 2 << "\t";
    for (int i = 3; i <= MAX; i = i + 2)
        if (factors[i] == 1)
            cout << i << "\t";
}

int main() {
    ll arr[] = {20, 10, 15, 60};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Prime factors in the LCM of the numbers of the array are :\n";
    printPrimeLCM(arr, n);
    return 0;
}

ผลลัพธ์

Prime factors in the LCM of the numbers of the array are : 2 3 5