ในปัญหานี้ เราได้รับอาร์เรย์ภายในช่วง 1 <=arr[i] <=10 12 . งานของเราคือพิมพ์ปัจจัยเฉพาะทั้งหมดของ LCM ขององค์ประกอบทั้งหมดของอาร์เรย์
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหาของเรา
Input: array = {2 , 5 , 15}
Output: 2 3 5
Explanation: LCM = 30
Factors of 30 = 2 * 3 * 5 ในการแก้ปัญหานี้ เราจะต้องหา LCM ของหลักอาร์เรย์ก่อน จากนั้นจึงหาตัวประกอบของ LCM และไพรม์จำนวนเฉพาะทั้งหมด
คอมไพเลอร์สามารถค้นหา LCM ของตัวเลขในลำดับ 10^6 ได้ยาก ดังนั้นเราจะใช้วิธีอื่นในการแก้ปัญหา
เราจะใช้แนวคิดที่ว่าตัวประกอบเฉพาะของตัวเลขจะเป็นตัวประกอบเฉพาะของ LCM ของพวกมันด้วย สำหรับสิ่งนี้ เราจะใช้การแยกตัวประกอบเฉพาะและค้นหาจำนวนเฉพาะโดยใช้ตะแกรงของอัลกอริทึม Sundaram
แล้วสร้างอาร์เรย์ปัจจัยซึ่งจะมีปัจจัยเฉพาะของ LCM ของตัวเลขในอาร์เรย์
โปรแกรมแสดงการใช้งานโซลูชันของเรา
ตัวอย่าง
#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
