Расчет функции Эйлера фи

Question

int phi (int n) { 
    int result = n; 
    for (int i=2; i*i<=n; ++i) 
     if (n % i == 0) { 
      while (n % i == 0) 
       n /= i; 
      result -= result/i; 
     } 
    if (n > 1) 
     result -= result/n; 
    return result; 
} 

я увидел над осуществлением Эйлера функции фи которая из O (SQRT п) .Я не получают факт использования i*i<=n в for цикле и необходимость от изменения n. Говорят, что это можно сделать за меньшее время O (sqrt n) Как? link (in Russian)

Answer 1

i*i<=n такой же, как i<= sqrt(n), из которого итерация продолжается только по заказу sqrt(n).

Используя прямое определение Euler totient function, вы должны найти простые числа, которые делят n.

Answer 2

Функция представляет собой прямую реализацию целочисленной факторизации путем пробного деления, за исключением того, что вместо того, чтобы сообщать о факторах, когда он их находит, функция использует факторы для вычисления phi. Вычисление phi может быть выполнено за время, меньшее O (sqrt n), используя лучший алгоритм для нахождения факторов; лучший способ сделать это зависит от величины n.

Answer 3

Если наибольшее количество (N говорят), что вы захотите, тотема достаточно мала, чтобы иметь в таблице таблицу размера N, то вы можете сделать намного лучше, за оценку, за счет для построения таблицы перед любыми оценками.

Один из подходов состоит в том, чтобы сначала создать таблицу простых чисел, а затем вместо использования пробного деления на каждое целое число не более sqrt (n) использовать пробное деление на каждое число не более sqrt (n).

Вы можете улучшить это, создав вместо таблицы простых чисел таблицу, которая дает (для каждого целого 2..N) наименьшее простое число, делящее число. Для построения такой таблицы может быть использована простая модификация обычного Sieve of Eratosthenes. Затем для вычисления тотамента числа вы используете таблицу, чтобы найти наименьшее число, делящее число (и накапливая это на вас), затем разделите число на запись в таблице, используя таблицу, чтобы найти наименьшее число, которое делит это, и так далее.