K-й наибольший множитель числа N

Даны два положительных целых числа N и K , задача состоит в том, чтобы вывести K-й наибольший множитель числа N.

Input: N = 12, K = 3
Output: 4
Explanation: The factors of 12 are {1, 2, 3, 4, 6, 12}. The largest factor is 12 and the 3^rd largest factor is 4.

Input: N = 30, K = 2
Output: 15
Explanation: The factors of 30 are {1, 2, 3, 5, 6, 10, 15, 30} and the 2^nd largest factor is 15.

Подход: Идея состоит в том, чтобы проверить каждое число в диапазоне [N, 1] и вывести K-е число, которое полностью делит N.

Итерация по циклу от N до 0 . Теперь для каждого числа в этом цикле:

• Проверьте, делит ли он N или нет.
• Если N делится на текущее число, уменьшите значение K на 1.
• Когда K становится равным 0, это означает, что текущее число является K- м наибольшим множителем N.
• Выведите ответ в соответствии с приведенным выше наблюдением.

Ниже приведена реализация вышеуказанного подхода:

Сложность времени:
Вспомогательное пространство:

Эффективный подход: проблема может быть решена оптимизированным способом по сложности sqrt(n) , используя тот факт, что множители любого числа остаются в виде пар . Другими словами, если i является множителем числа n , то n/i также будет множителем числа n . Итак, чтобы найти все множители числа, нам нужно проверить множители до sqrt(n) и их соответствующие пары. В статье используется аналогичный подход: найти делители натуральных чисел.

Иллюстрация:
Если n = 80, то все возможные пары делителей: (1,80), (2,40), (4,20), (5,16), (8,10). Следовательно, чтобы сохранить все множители 80, мы будем повторять цикл от 1 до √80 ≈ 8 и сохранять множители в диапазоне (который в данном случае включает 1,2,4,5,8). После этого мы запускаем обратный цикл и сохраняем пары этих предыдущих факторов (что даст 10, 16, 20, 40 и 80). Здесь мы запускаем обратный цикл, чтобы получить пары в возрастающем порядке. Таким образом, мы получим все множители, включающие {1, 2, 4, 5, 8, 10, 16, 20, 40 и 80}.

Подход:

1. Инициализируйте вектор, чтобы хранить элементы в возрастающем порядке.
2. Сначала выполните цикл от 1 до sqrt(n) и сохраните все факторы.
3. Затем повторите цикл в обратном порядке и для каждого фактора сохраните соответствующую пару. Итак, если я - фактор, сохраните n/i .
4. Если размер вектора больше или равен k, верните k-й наибольший фактор (который будет v[v.size()-k] , поскольку вектор v находится в порядке возрастания).
5. Если k элементов не существует, это означает, что нет k-го по величине фактора и, следовательно, возвращается -1 .

Обработка угловых случаев:
Крайний случай возникает, когда любой фактор точно равен sqrt (n). Например, если n=100, то в этом случае множителем числа будет 10, а также соответствующая ему пара 10 как (10*10=100). Таким образом, в этом случае 10 будет взято два раза. Чтобы решить этот случай, мы используем оператор if между двумя циклами и устраняем проблему, учитывая этот фактор только один раз.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (sqrt (n))
Вспомогательное пространство: O(m), где m — общее количество факторов n.