Сортировка чисел в лексикографическом порядке их простых множителей

Это звучит как проблема с разделами для меня. Первым шагом будет разбиение массива так, чтобы числа, делящиеся на 2, стояли первыми. Затем разделите эту группу на те, которые делятся на 2 во второй раз. Рекурсивно, пока у вас не будет пустой подгруппы. Теперь сделайте это снова с делителем 3. Продолжайте список простых чисел, пока не дойдете до sqrt(1e6) или пока не найдете все делители для каждого числа.

Поскольку вы уже хорошо уложились в отведенное вам время, вам просто нужен более эффективный способ хранения всех простых множителей для каждого числа, чтобы вы могли легко их найти. Вы можете сделать это с помощью двухуровневой таблицы поиска.

В одной таблице сохраните числа до 1e3 (1000) так, как вы их сейчас храните. Для этого потребуется массив 1e3 x 10 2d (1000 x 10 x 4 = 10000 байт).

Чтобы сохранить все простые множители для чисел до 1e6, вам нужно сохранить до 3 чисел для каждого (это 12 миллионов байт). Чтобы вычислить 3 числа, начните со списка простых множителей и перемножайте их до тех пор, пока вы не сможете умножить еще одно, не превысив 1000. Сохраните это в первой записи, затем сделайте то же самое с остатком и сохраните во втором числе. и если у вас осталось что-то, просто поместите его на 3-ю позицию (вам никогда не понадобится больше 3 - если бы у вас было 4, это означало бы, что последние два, умноженные вместе, будут больше 1000, что означало бы, что первые 2, умноженные вместе, будут быть ‹ 1000, в этом случае они не будут храниться отдельно). Если в списке есть простой множитель больше 1000, вам нужно только 2, потому что все остальные будут умножаться на ‹ 1000.

Чтобы получить исходный список простых множителей для записи, возьмите каждое из ваших трех чисел (которые будут простыми или составными числами 1000 или меньше или простыми числами> 1000), если они меньше 1000, найдите их простые множители в маленькой таблице и если не принимать их как есть, можно и восстановить список.

Например, для хранения 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)

Это будет работать, даже если список простых множителей не отсортирован.

На самом деле, простая модификация моего алгоритма помогла. Вместо того, чтобы сохранять первичную факторизацию каждого целого числа, я использовал то, что у меня уже было, а именно метод первичной факторизации, работающий за O(logn). Я создал собственный метод сортировки, который использует метод факторизации для факторизации двух целых чисел, сравнивая их простые множители. Следовательно, временная сложность осталась прежней, и не было необходимости хранить простую факторизацию любого целого числа.

Для тех, кому интересно узнать, как работает этот метод быстрой факторизации, вот ссылка ссылка (см. метод, использующий наименьшие делители).

Для будущих читателей, которые столкнутся с той же проблемой, вот мой принятый код:

#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;
}