Yenə ixtisar olunmayanlar (Həll təhlili)

Məxrəci $n$ olan düzgün ixtisar olunmayan $p/n$ kəsrlərinin sayı p < n olan və $p$-nin $n$ ilə qarşılıqlı sadə olduğu natural $p$ ədədlərinin sayına bərabərdir. Belə $p$ ədədlərinin sayı Eyler funksiyasına $\phi (n)$ bərabərdir.

Məxrəci $12$ olan bütün düzgün kəsrlərin çoxluğuna baxaq:

Kəsrləri ixtisar olunmayan formaya gətirdikdən sonra alırıq:

İndi bu kəsrləri məxrəclərinə görə qruplaşdıraq:

Bu məxrəclərin arasında $12$ ədədinin hər bir böləni $d$ ilə birlikdə $d$ ilə qarşılıqlı sadə olan $\varphi (d)$ sayda bütün sürətlər rast gəlinir. Başqa sözlə desək, $12$ ədədinin hər bir böləni $d$ üçün məxrəci $d$ olan düz $\varphi (d)$ sayda ixtisar olunmayan kəsr var.

İxtisardan sonra ilkin çoxluğun hər bir kəsri düz bir dəfə rast gəldiyi üçün alırıq:

Daha ümumi halda, əgər biz

düzgün kəsrlər ardıcıllığından başlayıb hər bir kəsri ixtisar olunmayan formaya gətirsək, aşağıdakı eyniliyi alarıq:

Nümunə

n = 12 olduqda \varphi(12) = 4 sayda düzgün ixtisar olunmayan kəsr mövcuddur:

Alqoritmin realizasiyası

euler funksiyası $\phi (n)$ qiymətini hesablayır.

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;
}

Proqramın əsas hissəsi. $n$ giriş qiymətini oxuyuruq və $\phi (n)$ nəticəsini çap edirik.

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

Java realizasiyası

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 realizasiyası

import math

euler funksiyası $\phi (n)$ qiymətini hesablayır.

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

Proqramın əsas hissəsi. $n$ giriş qiymətini oxuyuruq və $\phi (n)$ nəticəsini çap edirik.

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