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

Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение двух взаимно простых чисел по формуле:

т.е. при больших a и b, эта формула позволяет уменьшить вычислительную сложность.

Но если числа a и b не взаимно простые, то вычисления проводятся по обычной формуле.

Пример:

a=60 b=11. 60 и 11 – взаимно простые.

Как мы уже выяснили, для 60 число взаимно простых чисел равно 16, а для 11 равно 10.

т.е. , что гораздо легче вычислять, нежели «в лоб» от 660.

Дата добавления: 2014-01-15