Función Totient de Euler optimizada para evaluaciones múltiples

Posted on by Rudeus Greyrat

E uler T otient F unction (ETF) Φ(n) para una entrada n es el conteo de números en {1, 2, 3, …, n} que son primos relativos a n, es decir, los números cuyo MCD (máximo común divisor ) ) con n es 1. 
Ejemplos: 
 

Φ(5) = 4
gcd(1, 5) is 1, gcd(2, 5) is 1, 
gcd(3, 5) is 1 and gcd(4, 5) is 1

Φ(6) = 2
gcd(1, 6) is 1 and gcd(5, 6) is 1,

Hemos discutido diferentes métodos para calcular la función Euler Totient que funcionan bien para una sola entrada. En problemas en los que tenemos que llamar a la función Totient de Euler muchas veces, como 10 ^ 5 veces, la solución simple dará como resultado TLE (límite de tiempo excedido). La idea es utilizar Tamiz de Eratóstenes .
Encuentre todos los números primos hasta el límite máximo, digamos 10 ^ 5 usando Sieve of Eratosthenes . 
Para calcular Φ(n), hacemos lo siguiente. 
 

  1. Inicializar resultado como n.
  2. Iterar a través de todos los números primos menores o iguales a la raíz cuadrada de n (Aquí es donde es diferente de los métodos simples. En lugar de iterar a través de todos los números menores o iguales a la raíz cuadrada, iteramos solo a través de los números primos). Sea p el número primo actual. Verificamos si p divide a n, en caso afirmativo, eliminamos todas las ocurrencias de p de n al dividirlo repetidamente con n. También reducimos nuestro resultado por n/p (estos muchos números no tendrán GCD como 1 con n).
  3. Finalmente devolvemos resultado.

C++

// C++ program to efficiently compute values
// of euler totient function for multiple inputs.
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
const int MAX = 100001;
 
// Stores prime numbers upto MAX - 1 values
vector<ll> p;
 
// Finds prime numbers upto MAX-1 and
// stores them in vector p
void sieve()
{
    ll isPrime[MAX+1];
 
    for (ll i = 2; i<= MAX; i++)
    {
        // if prime[i] is not marked before
        if (isPrime[i] == 0)
        {
            // fill vector for every newly
            // encountered prime
            p.push_back(i);
 
            // run this loop till square root of MAX,
            // mark the index i * j as not prime
            for (ll j = 2; i * j<= MAX; j++)
                isPrime[i * j]= 1;
        }
    }
}
 
// function to find totient of n
ll phi(ll n)
{
    ll res = n;
 
    // this loop runs sqrt(n / ln(n)) times
    for (ll i=0; p[i]*p[i] <= n; i++)
    {
        if (n % p[i]== 0)
        {
            // subtract multiples of p[i] from r
            res -= (res / p[i]);
 
            // Remove all occurrences of p[i] in n
            while (n % p[i]== 0)
               n /= p[i];
        }
    }
 
    // when n has prime factor greater
    // than sqrt(n)
    if (n > 1)
       res -= (res / n);
 
    return res;
}
 
// Driver code
int main()
{
    // preprocess all prime numbers upto 10 ^ 5
    sieve();
    cout << phi(11) << "\n";
    cout << phi(21) << "\n";
    cout << phi(31) << "\n";
    cout << phi(41) << "\n";
    cout << phi(51) << "\n";
    cout << phi(61) << "\n";
    cout << phi(91) << "\n";
    cout << phi(101) << "\n";
    return 0;
}

Java

// Java program to efficiently compute values
// of euler totient function for multiple inputs.
import java.util.*;
 
class GFG{
static int MAX = 100001;
 
// Stores prime numbers upto MAX - 1 values
static ArrayList<Integer> p = new ArrayList<Integer>();
 
// Finds prime numbers upto MAX-1 and
// stores them in vector p
static void sieve()
{
    int[] isPrime=new int[MAX+1];
 
    for (int i = 2; i<= MAX; i++)
    {
        // if prime[i] is not marked before
        if (isPrime[i] == 0)
        {
            // fill vector for every newly
            // encountered prime
            p.add(i);
 
            // run this loop till square root of MAX,
            // mark the index i * j as not prime
            for (int j = 2; i * j<= MAX; j++)
                isPrime[i * j]= 1;
        }
    }
}
 
// function to find totient of n
static int phi(int n)
{
    int res = n;
 
    // this loop runs sqrt(n / ln(n)) times
    for (int i=0; p.get(i)*p.get(i) <= n; i++)
    {
        if (n % p.get(i)== 0)
        {
            // subtract multiples of p[i] from r
            res -= (res / p.get(i));
 
            // Remove all occurrences of p[i] in n
            while (n % p.get(i)== 0)
            n /= p.get(i);
        }
    }
 
    // when n has prime factor greater
    // than sqrt(n)
    if (n > 1)
    res -= (res / n);
 
    return res;
}
 
// Driver code
public static void main(String[] args)
{
    // preprocess all prime numbers upto 10 ^ 5
    sieve();
    System.out.println(phi(11));
    System.out.println(phi(21));
    System.out.println(phi(31));
    System.out.println(phi(41));
    System.out.println(phi(51));
    System.out.println(phi(61));
    System.out.println(phi(91));
    System.out.println(phi(101));
  
}
}
// this code is contributed by mits

Python3

# Python3 program to efficiently compute values
# of euler totient function for multiple inputs.
 
MAX = 100001;
 
# Stores prime numbers upto MAX - 1 values
p = [];
 
# Finds prime numbers upto MAX-1 and
# stores them in vector p
def sieve():
 
    isPrime = [0] * (MAX + 1);
 
    for i in range(2, MAX + 1):
         
        # if prime[i] is not marked before
        if (isPrime[i] == 0):
             
            # fill vector for every newly
            # encountered prime
            p.append(i);
 
            # run this loop till square root of MAX,
            # mark the index i * j as not prime
            j = 2;
            while (i * j <= MAX):
                isPrime[i * j]= 1;
                j += 1;
 
# function to find totient of n
def phi(n):
 
    res = n;
 
    # this loop runs sqrt(n / ln(n)) times
    i = 0;
    while (p[i] * p[i] <= n):
        if (n % p[i]== 0):
             
            # subtract multiples of p[i] from r
            res -= int(res / p[i]);
 
            # Remove all occurrences of p[i] in n
            while (n % p[i]== 0):
                n = int(n / p[i]);
        i += 1;
 
    # when n has prime factor greater
    # than sqrt(n)
    if (n > 1):
        res -= int(res / n);
 
    return res;
 
# Driver code
 
# preprocess all prime numbers upto 10 ^ 5
sieve();
print(phi(11));
print(phi(21));
print(phi(31));
print(phi(41));
print(phi(51));
print(phi(61));
print(phi(91));
print(phi(101));
 
# This code is contributed by mits

C#

// C# program to efficiently compute values
// of euler totient function for multiple inputs.
using System;
using System.Collections;
class GFG{
static int MAX = 100001;
 
// Stores prime numbers upto MAX - 1 values
static ArrayList p = new ArrayList();
 
// Finds prime numbers upto MAX-1 and
// stores them in vector p
static void sieve()
{
    int[] isPrime=new int[MAX+1];
 
    for (int i = 2; i<= MAX; i++)
    {
        // if prime[i] is not marked before
        if (isPrime[i] == 0)
        {
            // fill vector for every newly
            // encountered prime
            p.Add(i);
 
            // run this loop till square root of MAX,
            // mark the index i * j as not prime
            for (int j = 2; i * j<= MAX; j++)
                isPrime[i * j]= 1;
        }
    }
}
 
// function to find totient of n
static int phi(int n)
{
    int res = n;
 
    // this loop runs sqrt(n / ln(n)) times
    for (int i=0; (int)p[i]*(int)p[i] <= n; i++)
    {
        if (n % (int)p[i]== 0)
        {
            // subtract multiples of p[i] from r
            res -= (res / (int)p[i]);
 
            // Remove all occurrences of p[i] in n
            while (n % (int)p[i]== 0)
            n /= (int)p[i];
        }
    }
 
    // when n has prime factor greater
    // than sqrt(n)
    if (n > 1)
    res -= (res / n);
 
    return res;
}
 
// Driver code
static void Main()
{
    // preprocess all prime numbers upto 10 ^ 5
    sieve();
    Console.WriteLine(phi(11));
    Console.WriteLine(phi(21));
    Console.WriteLine(phi(31));
    Console.WriteLine(phi(41));
    Console.WriteLine(phi(51));
    Console.WriteLine(phi(61));
    Console.WriteLine(phi(91));
    Console.WriteLine(phi(101));
 
}
}
// this code is contributed by mits

PHP

<?php
// PHP program to efficiently compute values
// of euler totient function for multiple inputs.
 
$MAX = 100001;
 
// Stores prime numbers upto MAX - 1 values
$p = array();
 
// Finds prime numbers upto MAX-1 and
// stores them in vector p
function sieve()
{
    global $MAX,$p;
    $isPrime=array_fill(0,$MAX+1,0);
 
    for ($i = 2; $i<= $MAX; $i++)
    {
        // if prime[i] is not marked before
        if ($isPrime[$i] == 0)
        {
            // fill vector for every newly
            // encountered prime
            array_push($p,$i);
 
            // run this loop till square root of MAX,
            // mark the index i * j as not prime
            for ($j = 2; $i * $j<= $MAX; $j++)
                $isPrime[$i * $j]= 1;
        }
    }
}
 
// function to find totient of n
function phi($n)
{
    global $p;
    $res = $n;
 
    // this loop runs sqrt(n / ln(n)) times
    for ($i=0; $p[$i]*$p[$i] <= $n; $i++)
    {
        if ($n % $p[$i]== 0)
        {
            // subtract multiples of p[i] from r
            $res -= (int)($res / $p[$i]);
 
            // Remove all occurrences of p[i] in n
            while ($n % $p[$i]== 0)
            $n = (int)($n/$p[$i]);
        }
    }
 
    // when n has prime factor greater
    // than sqrt(n)
    if ($n > 1)
    $res -= (int)($res / $n);
 
    return $res;
}
 
// Driver code
  
    // preprocess all prime numbers upto 10 ^ 5
    sieve();
    print(phi(11)."\n");
    print(phi(21)."\n");
    print(phi(31)."\n");
    print(phi(41)."\n");
    print(phi(51)."\n");
    print(phi(61)."\n");
    print(phi(91)."\n");
    print(phi(101)."\n");
 
// this code is contributed by mits
?>

Javascript

<script>
 
// Javascript program to efficiently compute values
// of euler totient function for multiple inputs.
 
var MAX = 100001;
 
// Stores prime numbers upto MAX - 1 values
var p = [];
 
// Finds prime numbers upto MAX-1 and
// stores them in vector p
function sieve()
{
    var isPrime = Array(MAX+1).fill(0);
 
    for (var i = 2; i<= MAX; i++)
    {
        // if prime[i] is not marked before
        if (isPrime[i] == 0)
        {
            // fill vector for every newly
            // encountered prime
            p.push(i);
 
            // run this loop till square root of MAX,
            // mark the index i * j as not prime
            for (var j = 2; i * j<= MAX; j++)
                isPrime[i * j]= 1;
        }
    }
}
 
// function to find totient of n
function phi(n)
{
    var res = n;
 
    // this loop runs sqrt(n / ln(n)) times
    for (var i=0; p[i]*p[i] <= n; i++)
    {
        if (n % p[i]== 0)
        {
            // subtract multiples of p[i] from r
            res -= parseInt(res / p[i]);
 
            // Remove all occurrences of p[i] in n
            while (n % p[i]== 0)
            n = parseInt(n/p[i]);
        }
    }
 
    // when n has prime factor greater
    // than sqrt(n)
    if (n > 1)
    res -= parseInt(res / n);
 
    return res;
}
 
// Driver code
// preprocess all prime numbers upto 10 ^ 5
sieve();
document.write(phi(11)+ "<br>");
document.write(phi(21)+ "<br>");
document.write(phi(31)+ "<br>");
document.write(phi(41)+ "<br>");
document.write(phi(51)+ "<br>");
document.write(phi(61)+ "<br>");
document.write(phi(91)+ "<br>");
document.write(phi(101)+ "<br>");
 
// This code is contributed by rutvik_56.
</script>

Producción: 
 

10
12
30
40
32
60
72
100

Este artículo es una contribución de Abhishek Rajput . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *