我有 n 个整数存储在数组 a 中，比如 a[0],a[1],.....,a[n-1] 其中每个a[i] <= 10^12和n <100. 现在，我需要找到这 n 个整数的 LCM 的所有质因数，即 {a[0],a[1],.....,a[n-1]} 的 LCM
我有一种方法，但我需要一种更有效的方法。
我的方法：
First calculate all the prime numbers up to 10^6 using sieve of Eratosthenes.
For each a[i]
bool check_if_prime=1;
For all prime <= sqrt(a[i])
if a[i] % prime[i] == 0 {
store prime[i]
check_if_prime=0
}
if check_if_prime
store a[i] // a[i] is prime since it has no prime factor <= sqrt(n)
Print all the stored prime[i]'s
有没有更好的方法来解决这个问题？
我正在发布问题的链接：
http://www.spoj.pl/problems/MAIN12B/
链接到我的代码： http: //pastebin.com/R8TMYxNz
解决方案：
正如 Daniel Fischer 所建议的，我的代码需要一些优化，比如更快的筛子和一些小的修改。完成所有这些修改后，我能够解决问题。这是我在 SPOJ 上接受的代码，耗时 1.05 秒：
#include<iostream>
#include<cstdio>
#include<map>
#include<bitset>
using namespace std;
#define max 1000000
bitset <max+1> p;
int size;
int prime[79000];
void sieve(){
size=0;
long long i,j;
p.set(0,1);
p.set(1,1);
prime[size++]=2;
for(i=3;i<max+1;i=i+2){
if(!p.test(i)){
prime[size++]=i;
for(j=i;j*i<max+1;j++){
p.set(j*i,1);
}
}
}
}
int main()
{
sieve();
int t;
scanf("%d", &t);
for (int w = 0; w < t; w++){
int n;
scanf("%d", &n);
long long a[n];
for (int i = 0; i < n; i++)
scanf("%lld", &a[i]);
map < long long, int > m;
map < long long, int > ::iterator it;
for (int i = 0; i < n; i++){
long long num = a[i];
long long pp;
for (int j = 0; (j < size) && ((pp = prime[j]) * pp <= num); j++){
int c = 0;
for ( ; !(num % pp); num /= pp)
c = 1;
if (c)
m[pp] = 1;
}
if ((num > 0) && (num != 1)){
m[num] = 1;
}
}
printf("Case #%d: %d\n", w + 1, m.size());
for (it = m.begin(); it != m.end(); it++){
printf("%lld\n", (*it).first);
}
}
return 0;
}
如果有人能够以更好的方式或更快的方法做到这一点，请告诉我。