Объясните реализацию реализации Эйлера Totient

Question

Я видел этот код в платформе кодирования, чтобы эффективно вычислять время эйлера для разных значений. Я не в состоянии понять эту реализацию. Я действительно хочу научиться этому. Может ли кто-нибудь помочь мне объяснить это?

for(int i = 1; i < Maxn; i++) { // phi[1....n] in n * log(n)
   phi[i] += i;
   for(int j = 2 * i; j < Maxn; j += i) {
      phi[j] -= phi[i]; 
   }
}

Answer 1

Во-первых, отметим, что для простых значений p, phi(p) = p - 1.Это должно быть довольно интуитивно понятно, потому что все числа, меньшие простого числа, должны быть взаимно простыми с указанным простым числом.Итак, мы начинаем с нашего внешнего цикла for:

for(int i = 1; i < Maxn; i++) { // phi[1....n] in n * log(n)
   phi[i] += i;

Здесь мы добавляем значение i к phi(i).Для простого случая это означает, что нам нужно, чтобы phi(i) равнялось -1 заранее, а все остальные phi(i) должны быть дополнительно откорректированы, чтобы учесть количество взаимно простых чисел.Сосредоточив внимание на простом случае, давайте убедимся в том, что они равны -1.

Если мы пройдем цикл, в случае i=1 мы закончим итерацией по всем другим элементам нашего внутреннего циклавычитая 1.

   for(int j = 2 * i; j < Maxn; j += i) {
      phi[j] -= phi[i]; 
   }

Для любых других вычитаемых значений j должно равняться простому p.Но для этого потребуется j = 2 * i + i * k равным p для некоторой итерации k.Этого не может быть, потому что 2 * i + i * k == i * (2 + k), подразумевая, что p может быть равномерно разделен на i, что он не может (начиная с его простого числа).Таким образом, все phi(p) = p - 1.

Для не простых i нам нужно вычесть количество взаимно простых чисел.Мы делаем это во внутреннем цикле for.Повторное использование формулы из предыдущего, если i делит j, мы получим j / i = (2 + k).Таким образом, каждое значение меньше i можно умножить на (2 + k), чтобы оно было меньше j, но при этом иметь общий множитель (2 + k) с j (таким образом, не взаимно простое).

Однако, если мы вычтем (i - 1) множителей, содержащих (2 + k) множителей, мы посчитаем одни и те же факторы несколько раз.Вместо этого мы считаем только те, которые взаимно просты с i, или другими словами phi(i).Таким образом, у нас остается phi(x) = x - phi(factor_a) - phi(factor_b) ... для учета всех (2 + k_factor) кратных взаимных чисел, меньших, чем указанный фактор, который теперь имеет коэффициент (2 + k_factor) с x.

Поместив это в код, мы получим именно то, что у вас есть:

for(int i = 1; i < Maxn; i++) { // phi[1....n] in n * log(n)
   phi[i] += i;
   for(int j = 2 * i; j < Maxn; j += i) {
      phi[j] -= phi[i]; 
   }
}

Answer 2

Кстати, просто ради интереса есть и алгоритм O(n) для достижения того же. Мы знаем, что формула продукта Эйлера для totient составляет

phi(n) = n * product(
  (p - 1) / p)

  where p is a distinct prime that divide n

Например,

phi(18) = 18 * (
  (2-1)/2 * (3-1)/3)

        = 18 * 2/6
        = 18 * 1/3

  = 6

Теперь рассмотрим число m = n * p для некоторого простого p.

phi(n) = n * product(
  (p' - 1) / p')

  where p' is a distinct prime that divide n

Если p делит n, так как p уже появляется в расчете для phi(n), нам не нужно добавлять его в раздел продукта, мы просто добавляем его к начальному множителю

phi(m) = phi(p * n) = p * n * product(
  (p' - 1) / p')

       = p * phi(n)

В противном случае, если p не делит n, нам нужно использовать новое простое число,

phi(m) = phi(p * n) = p * n * product(
  (p' - 1) / p') * (p - 1) / p

       = p * (p - 1) / p * n * product(
  (p' - 1) / p')

       = (p - 1) * phi(n)

В любом случае, мы можем вычислить значение числа числа, умноженного на простое число, только из простого числа и собственного числа числа, которое можно агрегировать в O(n) путем многократного умножения чисел, которые мы сгенерировали до сих пор, на следующее простое число мы находим, пока не достигнем Maxn. Мы находим следующее простое число, увеличивая индекс до преемника, для которого мы не записали число (для него простое поколение является преимуществом).