Redaksiya

The number of regular irreducible fractions $p / n$ (with denominator $n$ ) is equal to the number of positive integers $p$ such that $p < n$ and $p$ is coprime with $n$ . The count of such numbers $p$ equals the Euler function $φ (n)$ .

Example

For $n = 12$ we have $φ (12) = 4$ regular irreducible fractions:

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

Algorithm realization

The euler function computes the value of $φ (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;
}

The main part of the program. Read the input value of $n$ and print $φ (n)$ .

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

Java realization

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 realization

import math

The euler function computes the value of $φ (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

The main part of the program. Read the input value of $n$ and print $φ (n)$ .

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