Поиск делителей

Пусть нам дано число $n$, и мы хотим найти все его делители.

Очевидно, что перебрав все числа от $1$ до $n$ и проверив делимость $n$ на каждое из них, мы получим ответ. Такой алгоритм будет иметь сложность $O(n)$ и это нас не очень-то устраивает.

Утверждение. Достаточно перебрать делители до $\sqrt{n}$

Действительно. Пусть мы нашли делитель $x$ и $x > \sqrt{n}$. Обозначим за $y$ число $\frac{n}{x}$. Тогда $xy = n$. Легко заметить, что $y < \sqrt{n}$ (пусть это не так и $y > \sqrt{n}$, тогда $xy > \sqrt{n} \sqrt{n} = n$, противоречие). А значит мы его уже рассмотрели.

Проверка на простоту

Определение. Целое положительное число называется простым, если оно имеет ровно два различных натуральных делителя — единицу и самого себя. Единица простым числом не считается.

Воспользуемся идеей перебора делителей до $\sqrt{n}$ и проверим наличие у числа делителей, отличных от $1$ и самого себя.

Факторизация

Определение. Факторизация целого числа - это представление этого числа в виде произведения простых.

Для этого алгоритма используем всё ту же идею. Если у числа есть делитель, отличный от $1$ и самого себя, то этот делитель или с ним сопряженный меньше $\sqrt{n}$.

Приведем реализацию алгоритма на абстрактном языке программирования

d := 2;

while d * d <= n do 
  if n mod d = 0 then
    n := n div d;
    writeln(d);    
  else
    d++;

if n != 1 then
    writeln(n);

Заметим, что если при факторизации числа $n$, мы нашли делитель $d$, то нам осталось факторизовать число $\frac{n}{d}$. Поэтому мы делим число $n$ на $d$ и продолжаем алгоритм. Начинать проверку делителей сначала не нужно, так как число $\frac{n}{d}$ гарантированно не имеет делителей меньше $d$, иначе мы бы их уже нашли при факторизации $n$.

Покажем так же, что все множители, найденные алгоритмом будут простыми. Заметим, что каждый раз алгоритм находит минимальный из всех делителей и делит на него $n$. А минимальный возможный делитель числа всегда является простым.

Обратим внимание на условие после цикла. Если у числа $n$ нет делителей меньше либо равных $\sqrt{n}$, то оно простое. Этот случай тут и обрабатывается.

Решето Эратосфена

Это алгоритм нахождения всех простых чисел от $1$ до $n$.

Основная его идея заложена в названии: давайте выпишем все числа $1, 2, … , n$ и будем вычеркивать (просеивать) те, которые точно простыми быть не могут.

Легко увидеть, что оставшиеся числа не имеют делителей отличных от себя и единицы, ведь все меньшие числа были рассмотрены, а кратные им вычеркнуты.

Оценим сложность полученного алгоритма

\[\sum_k \frac{n}{k} = \frac{n}{2} + \frac{n}{3} + \frac{n}{4} + \ldots + \frac{n}{n} = O(n \log n)\]

Некоторые идеи оптимизаций (на подумать)