Trong bài toán này, chúng ta được cho một mảng trong khoảng 1 <= arr[i] <= 1012. Nhiệm vụ là in ra tất cả các thừa số nguyên tố của LCM (bội chung nhỏ nhất) của tất cả các phần tử trong mảng.
Hãy xem ví dụ sau để hiểu rõ vấn đề:
Input: array = {2 , 5 , 15} Output: 2 3 5 Giải thích: LCM = 30 Thừa số của 30 = 2 * 3 * 5Để giải quyết, chúng ta phải tìm LCM của các phần tử mảng rồi tìm thừa số của LCM và lọc ra các số nguyên tố.
Việc tìm LCM trực tiếp có thể tốn nhiều tài nguyên cho các số lớn (thứ 10^6). Do đó, ta sử dụng cách khác: thừa số nguyên tố của các số cũng sẽ là thừa số nguyên tố của LCM của chúng. Ta dùng phân tích thừa số nguyên tố và tìm các số nguyên tố bằng sàng Sundaram.
Sau đó tạo mảng dấu hiệu chứa các thừa số nguyên tố của LCM các số trong mảng.
Chương trình minh họa triển khai giải pháp:
Ví dụ
#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<<"Các thừa số nguyên tố trong LCM của các số trong mảng là :\n"; printPrimeLCM(arr, n); return 0; }Kết quả
Các thừa số nguyên tố trong LCM của các số trong mảng là : 2 3 5