Факторизация. Мультипликативная функция

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

       Построим вычисление факторизации по массиву lp. Отмечу, что можно отказаться от деления в алгоритме, если в решете подсчитать массив множителей x. Факторизацию мы подсчитаем за логарифмическое время (количество простых делителей числа).

Мультипликативная функция

это функция у которой выполняются следующие свойства

1) f(1) = 1

2) f(x*y) = f(x) * f(y), если gcd(x, y) = 1

Примеры

● f(x) = x

● f(x) = x == 1

● f(x) = 1

● O0(x) - количество делителей числа x. Если a и b взаимно просты, то каждый делитель произведения a*b может быть единственным образом представлен в виде произведения делителей a и b, и обратно, каждое такое произведение является делителем a*b. Отсюда следует, что функция τ мультипликативна.

● O1(x) - сумма делителей числа x. Верно по тем же соображениям

● pfi(x) - функция эйлера, количество эйлера, от 1 до x, что взаимно просты с x, доказали ранее

Мультипликативные функции можно считать с помощью линейного решета Эратосфена особенно если для степеней простых чисел данная функция считается просто. Пусть нам нужно f(i), если i = p**k * j, где p минимальный простой делитель i, в степени равной степени его вхождения в факторизацию. Тогда то f(i) = f(p**k) * f(j), в линейном решете можно хранить не только минимальный простой делитель, но и сколько раз он входит в число.

Приведём реализацию функции Эйлера, и использованием массива lp, но без дополнительных предподсчётов, которые могли бы ускорить решение - асимптотика уже будет за логарифм.