Сортировка по возрастанию наименьшего кратного числа

Question

Мне нужно отсортировать массив по возрастанию наименьшего кратного. Должно быть так (1 2 4 100 3 15 29..) Т.е 1 всегда будет слева, далее идут цифры которые кратные 2-м(2,4,100), потом цифры которые кратные 3-м(3,15) и число 29 должно находится в правой части т.к оно делится только на 29 и т.д. Я не могу понять как сделать такую сортировку. Как мне с начало проверить числа которые кратные 2-м а потом кратные 3-м и т.д?? Буду благодарен если хотя-бы подскажите как это реализовать!

Answer 1

В лоб решение -- написать функцию, определяющую для каждого числа наименьший простой множитель, и использовать её в предикате для сортировки (функтор std::sort).

Не в лоб, но с меньшей сложностью -- перебирая простые множители, переставлять (через std::swap) в начало массива числа, на них дделящиеся, а остальные оставлять в конце; на каждом следующем проходе брать индекс или итератор с учётом предыдущего шага так, чтобы ичключить числа, уже находящиеся на своём месте.

Простые числа можно получать тут же по ходу решетом Эратосфена, можно заранее, можно и не получать (брать все числа подряд, алгоритм просто не сработает для составных).

Answer 2

int mdiv(int n)
{
    if (n%2 == 0) return 2;
    for(unsigned int i = 3; i*i <= n; i+=2)
        if (n%i == 0) return i;
    return n;
}

....

sort(begin(array),end(array),
           [](int a, int b){ int m = mdiv(a), n = mdiv(b);
           return m < n ? true : m > n ? false : a < b; });

Полный код - https://ideone.com/6CGsFf

БЛОГ НА HUSL

Сортировка по возрастанию наименьшего кратного числа

Ответы (2 шт):