Разбор

Количество правильных несократимых дробей $p / n$ (со знаменателем $n$ ) равно количеству таких натуральных чисел $p$ , что $p < n$ и $p$ взаимно просто с $n$ . Такое количество чисел $p$ равно функции Эйлера $φ (n)$ .

Пример

При $n = 12$ имеются $φ (12) = 4$ правильные несократимые дроби:

\frac{1}{12}, \frac{5}{12}, \frac{7}{12}, \frac{11}{12}

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

Функция euler вычисляет значение $φ (n)$ .

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

Основная часть программы. Читаем входное значение $n$ и выводим $φ (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 <= n;i++)
    {
      if (n % i == 0) result -= result / i;
      while (n % i == 0) n /= i;
    }
    if (n > 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 вычисляет значение $φ (n)$ .

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

Основная часть программы. Читаем входное значение $n$ и выводим $φ (n)$ .

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