339. Again irreducible

The fraction m / n is called regular irreducible, if 0 < m < n and GCD(m, n) = 1. Find the number of regular irreducible fractions with the denominator n.

Input. Each line is a separate test case that contains one integer n (n < 10⁹). The last line contains 0 and is not processed. The number of test cases is no more than 100.

Output. For each value of n print in a separate line the number of regular irreducible fractions with the denominator n.

Sample input	Sample output
12 123456 7654321 0	4 41088 7251444

SOLUTION

number theory

Algorithm analysis

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 j(n).

Example

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

Algorithm realization

The euler function computes the value of j(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 j(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 j(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 j(n).

while True:

n = int(input())

if n == 0: break

print(euler(n))