Рубрики

Функция Эйлера для всех чисел, меньших или равных n

Функция Totient Эйлера Φ (n) для входа n — это число чисел в {1, 2, 3,…, n}, которые являются относительно простыми по отношению к n, т. Е. Числа, чей GCD (Величайший общий делитель) с n равен 1.

Например, Φ (4) = 2, Φ (3) = 2 и Φ (5) = 4. Существует 2 числа, меньших или равных 4, которые относительно просты по отношению к 4, 2 числа, меньших или равных 3, которые относительно простое число до 3. И 4 числа, меньшие или равные 5, которые относительно просты до 5.

Мы обсудили различные методы вычисления Φ (n) в предыдущем посте .

Как вычислить Φ для всех чисел, меньших или равных n?
Пример:

Input: n = 5
Output: Totient of 1 is 1
        Totient of 2 is 1
        Totient of 3 is 2
        Totient of 4 is 2
        Totient of 5 is 4 

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Простое решение — вызвать Φ (i) для i = 1 к n.

Эффективное решение заключается в использовании идеи, аналогичной Sieve of Eratosthenes, для предварительного вычисления всех значений /. Метод основан на формуле продукта ниже.

Формула в основном говорит, что значение Φ (n) равно n, умноженному на произведение (1 — 1 / p) для всех простых факторов p числа n. Например, значение Φ (6) = 6 * (1-1 / 2) * (1 — 1/3) = 2.

Ниже приведен полный алгоритм:

1) Create an array phi[1..n] to store Φ values of all numbers 
   from 1 to n.  

2) Initialize all values such that phi[i] stores i.  This
   initialization serves two purposes.
   a) To check if phi[i] is already evaluated or not. Note that
      the maximum possible phi value of a number i is i-1.
   b) To initialize phi[i] as i is a multiple in above product
      formula. 

3) Run a loop for p = 2 to n
    a) If phi[p] is p, means p is not evaluated yet and p is a 
       prime number (slimier to Sieve), otherwise phi[p] must 
       have been updated in step 3.b
    b) Traverse through all multiples of p and update all 
       multiples of p by multiplying with (1-1/p).

4) Run a loop from i = 1 to n and print all Ph[i] values. 

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для вычисления функции Totient для
// все числа, меньшие или равные n.
#include<iostream>

using namespace std;

  
// Вычисляет и печатает число всех чисел
// меньше или равно n.

void computeTotient(int n)

{

    // Создать и инициализировать массив для хранения

    // фи или суммарные значения

    long long phi[n+1];

    for (int i=1; i<=n; i++)

        phi[i] = i; // указывает, что еще не оценен

                    // и инициализирует для продукта

                    // формула

  

    // Вычисляем другие значения Phi

    for (int p=2; p<=n; p++)

    {

        // Если фи [р] еще не вычислена,

        // тогда число p простое

        if (phi[p] == p)

        {

            // Фи простого числа р

            // всегда равно p-1.

            phi[p] = p-1;

  

            // Обновляем значения фи всех

            // кратно p

            for (int i = 2*p; i<=n; i += p)

            {

               // Добавить вклад р в его

               // умножаем i, умножая на

               // (1 - 1 / р)

               phi[i] = (phi[i]/p) * (p-1);

            }

        }

    }

  

    // Печатать предварительно вычисленные значения phi

    for (int i=1; i<=n; i++)

      cout << "Totient of " << i << " is "

           << phi[i] << endl;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int n = 12;

    computeTotient(n);

    return 0;

}

Джава

// Java-программа для вычисления Totient
// функция для всех чисел меньшего размера
// чем или равно n.

import java.util.*;

  

class GFG {

      
// Вычисляет и печатает число всех чисел
// меньше или равно n.

static void computeTotient(int n) {

      

    // Создать и инициализировать массив для хранения

    // фи или суммарные значения

    long phi[] = new long[n + 1];

    for (int i = 1; i <= n; i++)

    phi[i] = i; // указывает, что еще не оценен

                // и инициализирует для продукта

                // формула

  

    // Вычисляем другие значения Phi

    for (int p = 2; p <= n; p++) {

          

    // Если фи [р] еще не вычислена,

    // тогда число p простое

    if (phi[p] == p) {

          

        // Фи простого числа р

        // всегда равно p-1.

        phi[p] = p - 1;

  

        // Обновляем значения фи всех

        // кратно p

        for (int i = 2 * p; i <= n; i += p) {

              

        // Добавить вклад р в его

        // умножаем i, умножая на

        // (1 - 1 / р)

        phi[i] = (phi[i] / p) * (p - 1);

        }

    }

    }

  

    // Печатать предварительно вычисленные значения phi

    for (int i = 1; i <= n; i++)

    System.out.println("Totient of " + i +

                         " is " + phi[i]);

}

  
// Код драйвера

public static void main(String[] args) {

      

    int n = 12;

    computeTotient(n);

}
}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python программа для вычисления
# Тотальная функция для
# все числа меньше чем
# или равно n.

  
# Вычисляет и печатает
# число всех чисел
# меньше или равно n.

def computeTotient(n):

  

    # Создать и инициализировать

    # массив для хранения

    # фи или суммарные значения

    phi=[]

    for i in range(n + 2):

        phi.append(0)

  

    for i in range(1, n+1):

  

        phi[i] = i # указывает, что еще не оценен

                    # и инициализирует для продукта

                    # формула.

   

    # Вычислить другие значения Phi

    for p in range(2,n+1):

      

        # Если фи [р] еще не вычислена,

        # тогда число p простое

        if (phi[p] == p):

          

            # Фи простого числа р

            # всегда равно р-1.

            phi[p] = p-1

   

            # Обновить значения фи всех

            # кратно р

            for i in range(2*p,n+1,p):

              

                # Добавить вклад р в его

                # кратный я умножением на

                # (1 - 1 / р)

                phi[i] = (phi[i]//p) * (p-1)

      

   

    # Печать предварительно вычисленных значений фи

    for i in range(1,n+1):

        print("Totient of ", i ," is ",

           phi[i])

  
# Код драйвера

  

n = 12

computeTotient(n)

  
# Этот код добавлен
# Анант Агарвал

C #

// C # программа для проверки, если задано два
// строки на расстоянии один.

using System;

  

class GFG

{

      
// Вычисляет и печатает все
// числа, меньшие или равные n

static void computeTotient(int n) 

{

      

    // Создать и инициализировать массив

    // сохраняем значения phi или totient

    long []phi = new long[n + 1];

    for (int i = 1; i <= n; i++)

      

    // указывает, что еще не оценен

    // и инициализирует для продукта

    // формула

    phi[i] = i; 

      

    // Вычисляем другие значения Phi

    for (int p = 2; p <= n; p++) 

    {

          

    // Если фи [р] еще не вычислена,

    // тогда число p простое

    if (phi[p] == p) 

    {

          

        // Фи простого числа р

        // всегда равно p-1.

        phi[p] = p - 1;

  

        // Обновляем значения фи всех

        // кратно p

        for (int i = 2 * p; i <= n; i += p) 

        {

              

        // Добавить вклад р в его

        // умножаем i, умножая на

        // (1 - 1 / р)

        phi[i] = (phi[i] / p) * (p - 1);

          

        }

    }

    }

  

    // Печатать предварительно вычисленные значения phi

    for (int i = 1; i <= n; i++)

    Console.WriteLine("Totient of " + i +" is " + phi[i]);

}

  
// Код драйвера

public static void Main()

{

      

    int n = 12;

    computeTotient(n);

}
}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP программа для вычисления Totient
// функция для всех чисел меньшего размера
// чем или равно n.

  
// Вычисляет и печатает totient
// всех чисел меньше чем
// или равно n.

function computeTotient($n)

{

      

    // Создать и инициализировать

    // массив для хранения

    // фи или суммарные значения

    for($i = 1; $i <= $n; $i++)

      

        // указывает, что еще не оценен

        // и инициализирует для продукта

        // формула

        $phi[$i] = $i

  

    // Вычисляем другие значения Phi

    for($p = 2; $p <= $n; $p++)

    {

          

        // Если фи [р] еще не вычислена,

        // тогда число p простое

        if ($phi[$p] == $p)

        {

              

            // Фи простого числа р

            // всегда равно p-1.

            $phi[$p] = $p - 1;

  

            // Обновляем значения фи всех

            // кратно p

            for($i = 2 * $p; $i <= $n; $i += $p)

            {

                  

                // Добавить вклад р в его

                // умножаем i, умножая на

                // (1 - 1 / $ p)

                $phi[$i] = ($phi[$i] / $p) * ($p - 1);

            }

        }

    }

  

    // Печатать предварительно вычисленные значения phi

    for($i = 1; $i <= $n; $i++)

    echo "Totient of " , $i , " is ",

        $phi[$i] ,"\n";

}

  

    // Код драйвера

    $n = 12;

    computeTotient($n);

  
// Этот код предоставлен ajit
?>


Выход:

Totient of 1 is 1
Totient of 2 is 1
Totient of 3 is 2
Totient of 4 is 2
Totient of 5 is 4
Totient of 6 is 2
Totient of 7 is 6
Totient of 8 is 4
Totient of 9 is 6
Totient of 10 is 4
Totient of 11 is 10
Totient of 12 is 4

То же решение можно использовать, когда у нас есть большое количество запросов для вычисления функции toentent.

Эта статья предоставлена Ekta Goel . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Функция Эйлера для всех чисел, меньших или равных n

0.00 (0%) 0 votes