Эффективное нахождение всех различных делителей числа, т.е. натурального числа!

Эффективное нахождение всех различных делителей числа, т.е. натурального числа!

Говорят, что число x является делителем натурального числа n, если при делении n на x в остатке возвращается 0. т. е. n % x == 0.

Например, делителями числа 12 являются 1, 2, 3, 4, 6 и 12.

Теперь, чтобы найти делители числа n в программировании, на первый взгляд, мы можем применить наивный подход перебора всех целочисленных значений, начиная с 1 до n и проверьте, делится ли оно на n. Если да, то посчитайте и двигайтесь дальше. Давайте иметь четкую концепцию, принимая n = 12.

[Здесь a|b означает «а делит b», а a∤b означает «а не делит b»]

when i = 1, 1|12
when i = 2, 2|12
when i = 3, 3|12
when i = 4, 4|12
when i = 5, 5∤12
when i = 6, 6|12
when i = 7, 7∤12
when i = 8, 8∤12
when i = 9, 9∤12
when i = 10, 10∤12
when i = 11, 11∤12
when i = 12, 12|12

Итак, мы нашли 1, 2, 3, 4, 6 и 12 как делители. Теперь давайте посмотрим на C++,

Временная сложность приведенной выше программы составляет O (n). Поэтому, если вы укажете значение, например, 10⁹ или достаточно большое, это займет разумное время. К счастью, мы можем улучшить эту временную сложность с O(n) до O(√n). Как?

Для этого нам нужно что-то наблюдать!

Если вы посмотрите на приведенный выше пример, вы увидите, что все делители идут парами.Математически, когда | b и a/b = c, тогда c | б тоже верно. Таким образом, b и c являются делителями a.

В предыдущем примере, когда вы разделили 12 на 1, частное будет 12/1 = 12, что также является делителем 12. Снова разделив 12 на 2, вы получите частное 12/2 = 6, что также является делителем 12. То же самое продолжается.

when i = 1, 1|12 and 12/1 = 12
when i = 2, 2|12 and 12/2 = 6
when i = 3, 3|12 and 12/3 = 4

Здесь мы получаем пары (1, 12), (2, 6), (3, 4), которые являются делителями 12 всего за три итерации.

Теперь, чтобы узнать точное количество итераций, необходимых для нахождения всех делителей, вы можете случайным образом взять некоторые целые значения и найти все делители предыдущим способом. Наконец, вы должны заметить одну вещь: на самом деле вы выполняете итерацию не более чем sqrt(n) из 1 таким образом (Вы можете доказать это математически? Надеюсь, вы это сделаете!).

Теперь давайте перейдем к коду —

Теперь найдите делители для различных целых чисел, и вы увидите скорость этой программы, использующей этот процесс.

Временная сложность приведенной выше программы или алгоритма составляет O(√n).