Знову нескоротні (Розбір)

Кількість правильних нескоротних дробів $p/n$ (зі знаменником $n$) рівна кількості таких натуральних чисел $p$, що p \u003c n і $p$ взаємно просте з $n$. Така кількість чисел $p$ рівна функції Ейлера $\phi (n)$.

Розглянемо множину всіх правильних дробів зі знаменником $12$:

Після скорочення дробів до нескоротного вигляду отримуємо:

Тепер згрупуємо ці дроби за їхніми знаменниками:

Серед цих знаменників зустрічається кожен дільник $d$ числа $12$ разом із усіма $\varphi (d)$ чисельниками, взаємно простими з $d$. Іншими словами, для кожного дільника $d$ числа $12$ існує рівно $\varphi (d)$ нескоротних дробів зі знаменником $d$.

Оскільки після скорочення кожен дріб із вихідної множини зустрічається рівно один раз, отримуємо:

У більш загальному випадку, якщо ми почнемо з послідовності правильних дробів

і скоротимо кожен дріб до нескоротного вигляду, то отримаємо наступну тотожність:

Приклад

При n = 12 маємо \varphi(12) = 4 правильні нескоротні дроби:

Реалізація алгоритму

Функція euler обчислює значення $\phi (n)$.

int euler(int n)
{
  int i, result = n;
  for (i = 2; i * i \u003c= n; i++)
  {
    if (n % i == 0) result -= result / i;
    while (n % i == 0) n /= i;
  }
  if (n \u003e 1) result -= result / n;
  return result;
}

Основна частина програми. Читаємо вхідне значення $n$ і виводимо $\phi (n)$.

while(scanf("%d",&n),n)
  printf("%d\n",euler(n));

Java реалізація

import java.util.Scanner;

public class Main
{
  static int euler(int n)
  {
    int result = n;
    for(int i = 2; i * i \u003c= n;i++)
    {
      if (n % i == 0) result -= result / i;
      while (n % i == 0) n /= i;
    }
    if (n \u003e 1) result -= result / n;
    return result;
  }
    
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    while(con.hasNext())
    {
      int n = con.nextInt();
      if (n == 0) break;
      System.out.println(euler(n));
    }
    con.close();
  }
}

Python реалізація

import math

Функція euler обчислює значення $\phi (n)$.

def euler(n):
  result = n
  i = 2
  while i \u003c= math.isqrt(n):
    if n % i == 0:
      result -= result // i
      while n % i == 0: n //= i
    i += 1
  if n \u003e 1: result -= result // n
  return result

Основна частина програми. Читаємо вхідне значення $n$ і виводимо $\phi (n)$.

while True:
  n = int(input())
  if n == 0: break
  print(euler(n))