按素数的字典顺序对数字进行排序

Question

我正在尝试解决一个算法问题，该问题要求我根据素因子的字典顺序对大小为 N (N <= 1e6) 的数字列表进行排序。列表中的每个数字都在 [2,1e6].

中

Link 有问题。

例如，

2 3 4 5 6

将排序为：

2 4 6 3 5

它们的质因数如下所示：

我的尝试：

我能够通过对每个数字使用 O(logn) 素数分解方法并将其存储到 1e6 * 21 二维数组中来为此设计一个正确的解决方案，因为所有 <= 1e6 的数字最多可以有20 个素因数 2^20 > 1e6.

之后我使用这些素数的字典顺序对每个数字进行排序。

我的程序能够运行在 2 秒的时间限制内完成，但使用了太多内存（内存限制为 32mb）。

有人能告诉我解决这个问题的更好方法吗？

p.s。这个问题被标记为 "depth-first-search" 但我看不出它是如何工作的。

Answer 1

对我来说，这听起来像是一个分区问题。第一步是对数组进行分区，以便除以 2 的数字排在第一位。然后将 that 分组，再除以 2。递归直到你有一个空的子组。现在用 3 的除数再做一次。继续素数列表，直到到达 sqrt(1e6) 或找到每个数字的所有除数。

Answer 2

由于您已经在您的时间限制内，您只需要一种更有效的方法来存储每个数字的所有质因数，以便您可以轻松地查找它们。您可以使用 2 级查找 table.

在一个 table 中，存储最多 1e3 (1000) 个数字，就像您现在存储的那样。这将需要一个 1e3 x 10 二维数组（1000 x 10 x 4 = 10000 字节）。

要存储最大为 1e6 的数字的所有素因数，您需要为每个数字存储最多 3 个数字（即 1200 万字节）。要计算这 3 个数字，请从素数列表开始，然后将它们相乘，直到您不能在不超过 1000 的情况下再乘以另一个数。将其存储在第一个条目中，然后对余数执行相同操作并存储在第二个数字中如果你还有剩下的，就把它放在第 3 个位置（你永远不需要超过 3 个——如果你有 4 个，这意味着最后两个相乘将超过 1000，这意味着前 2 个相乘将< 1000，在这种情况下它们不会单独存储）。如果列表中有一个超过 1000 的质因数，则您只需要 2，因为所有其他因素都会相乘到 < 1000。

要检索条目的原始质因数列表，请取三个数字中的每一个（这将是质数或合数 1000 或更小或质数 > 1000），如果它们小于 1000，请查找它们的质因数在小 table 中，如果不按原样使用，您可以重建列表。

例如存储 515130 (2*3*5*7*11*223)

1st number: 210 (2*3*5*7) can't multiply by 11 without going over 1000
2nd number: 11 (prime) can't multiply by 223 without going over
3rd number: 223

667023 (3*7*23*1381)

1st: 438 (3*7*23)
2nd: 1381 (prime)

即使质因数列表未排序，这仍然有效。

Answer 3

实际上，对我的算法进行简单修改就可以解决问题。我没有存储每个整数的质因数分解，而是利用了我已有的，这是一种在 O(logn) 中有效的质因数分解方法。我创建了一个自定义排序方法，该方法使用因式分解方法对两个整数进行因式分解，同时比较它们的质因数。因此，时间复杂度保持不变，无需存储任何整数的质因数分解。

对于那些想知道这种快速分解方法如何工作的人，这里有一个 link（请参阅使用最低除数的方法）。

对于未来遇到同样问题的读者，这是我接受的代码：

#include<cstdio>
#include<algorithm>

#define FACTOR_LIM (int) 1e6+2 // used by preFactor(n). Defined as <= n <= 1e8

using namespace std;

int lowestDiv[FACTOR_LIM+1], a[FACTOR_LIM], n;

void preFactor(int n) {
    int root = 2;
    for(int i = 2; i*i <= n; i++) {
        if(lowestDiv[i]) continue;
        root = lowestDiv[i] = i;
        for(int j = i*i; j <= n; j+=i) {
            lowestDiv[j] = (lowestDiv[j]) ? lowestDiv[j] : i;
        }
    }
    for(int i = root; i <= n; i++) {
        if(!lowestDiv[i]) {
            lowestDiv[i] = i;
        }
    }
}

bool cmp(const int i, const int j) {
    int x = i, y = j;
    while (x != y) {
        int p = lowestDiv[x];
        int q = lowestDiv[y];
        if (p != q) return p < q;
        x /= p;
        y /= q;
    }
    return false;
}

int main() {
    preFactor(FACTOR_LIM-1);
    scanf("%d",&n);

    for(int i = 0; i < n; i++) {
        scanf("%d",&a[i]);
    }
    sort(a,a+n,cmp);

    for(int i = 0; i < n; i++) {
        printf("%d\n",a[i]);
    }
    return 0;
}

按素数的字典顺序对数字进行排序

Sort numbers in lexicographical order of their prime factors

algorithm

sorting

math

depth-first-search

prime-factoring