c++ - 如何计算n个整数的lcm的所有质因数？

Question

我有 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;
}

如果有人能够以更好的方式或更快的方式做到这一点，请告诉我。

Answer 1

在这些限制下，一些不太大的数字，找到其最小公倍数的质因数分解的最佳方法确实是每个数字的因式分解。由于只有 78498 个小于 10⁶ 的素数，试验除法将足够快(除非你真的对性能的最后一滴绝望)，并将素数筛选到 10⁶ 也是几毫秒的事情。

如果速度是最重要的，那么将试验划分和确定性 Miller-Rabin 型素数检验与 Pollard 的 rho 算法或椭圆曲线分解方法等分解方法相结合的方法可能会更快一些(但数字非常小，差异不会很大，您需要一个超过 64 位的数字类型，以便快速进行素性测试和因式分解)。

在因式分解中，您当然应该删除找到的质因数

if (a[i] % prime[k] == 0) {
    int exponent = 0;
    do {
        a[i] /= prime[k];
        ++exponent;
    }while(a[i] % prime[k] == 0);
    // store prime[k] and exponent
    // recalculate bound for factorisation
}

减少您需要检查素数的限制。

据我所知，您的主要问题是您的筛子太慢并且占用了太多空间(这在一定程度上导致了它的缓慢)。使用位筛获得更好的缓存局部性，从筛中移除偶数并停止检查是否在 max 的平方根处划掉倍数.而且您为素数数组分配了太多空间。

for(int j=0;(prime[j]*prime[j] <= num) && (j<size);j++){

你必须检查j < size在访问 prime[j] 之前.

    while(num%prime[j]==0){
        c=1;
        num /= prime[j];
        m[prime[j]]=1;
    }

不要设置 m[prime[j]]多次。即使std::map s 非常快，比只设置一次要慢。