Un número altamente totiente k es un entero que tiene más soluciones a la ecuación φ(x) = k, donde φ es la función totiente de Euler
La secuencia:
1, 2, 4, 8, 12, 24, 48, 72, 144, 240, 432, 480, 576, 720, 1152, 1440, 2880, 4320, 5760, 8640
Explicación :
- 1 tiene 2 soluciones
- 2 tiene 3 soluciones
- 4 tiene 4 soluciones
- 8 tiene 5 soluciones
- 12 tiene 6 soluciones
- 24 tiene 10 soluciones
Para un N dado , la tarea es imprimir los primeros N números altamente útiles.
Ejemplos:
Entrada: N = 10
Salida: 1, 2, 4, 8, 12, 24, 48, 72, 144, 240
Entrada: N = 20
Salida: 1, 2, 4, 8, 12, 24, 48, 72, 144 , 240, 432, 480, 576, 720, 1152, 1440, 2880, 4320, 5760, 8640
Enfoque:
Un enfoque eficiente es almacenar todos los valores de φ(x) hasta 10 5 en un mapa junto con sus frecuencias y luego ejecutar un bucle desde 1 hasta que el recuento del número de pacientes sea menor que N . Para cada i , verificaremos si la frecuencia de i es mayor que el elemento anterior, si es así, imprima el número y aumente el conteo; de lo contrario, incremente el número.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find highly totient numbers #include <bits/stdc++.h> using namespace std; // Function to find euler totient number int phi(int n) { int result = n; // Initialize result as n // Consider all prime factors of n and // subtract their multiples from result for (int p = 2; p * p <= n; ++p) { // Check if p is a prime factor. if (n % p == 0) { // If yes, then update n and result while (n % p == 0) n /= p; result -= result / p; } } // If n has a prime factor greater than sqrt(n) // (There can be at-most one such prime factor) if (n > 1) result -= result / n; return result; } // Function to find first n highly totient numbers void Highly_Totient(int n) { // Count of Highly totient numbers // and value of count of phi of previous numbers int count = 0, p_count = -1, i = 1; // Store all the values of phi(x) upto // 10^5 with frequencies map<int, int> mp; for (int i = 1; i < 100000; i++) mp[phi(i)]++; while (count < n) { // If count is greater than count of // previous element if (mp[i] > p_count) { // Display the number cout << i; if(count < n-1) cout << ", "; // Store the value of phi p_count = mp[i]; count++; } i++; } } // Driver code int main() { int n = 20; // Function call Highly_Totient(n); return 0; }
Java
// Java program to find highly totient numbers import java.util.*; class GFG { // Function to find euler totient number static int phi(int n) { int result = n; // Initialize result as n // Consider all prime factors of n and // subtract their multiples from result for (int p = 2; p * p <= n; ++p) { // Check if p is a prime factor. if (n % p == 0) { // If yes, then update n and result while (n % p == 0) n /= p; result -= result / p; } } // If n has a prime factor greater than sqrt(n) // (There can be at-most one such prime factor) if (n > 1) result -= result / n; return result; } // Function to find first n highly totient numbers static void Highly_Totient(int n) { // Count of Highly totient numbers // and value of count of phi of previous numbers int count = 0, p_count = -1; // Store all the values of phi(x) upto // 10^5 with frequencies HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); for (int i = 1; i < 100000; i++) { if(mp.containsKey(phi(i))) { mp.put(phi(i), mp.get(phi(i)) + 1); } else { mp.put(phi(i), 1); } } int i = 1; while (count < n) { // If count is greater than count of // previous element if (mp.containsKey(i)&&mp.get(i) > p_count) { // Display the number System.out.print(i); if(count < n - 1) System.out.print(", "); // Store the value of phi p_count = mp.get(i); count++; } i++; } } // Driver code public static void main(String[] args) { int n = 20; // Function call Highly_Totient(n); } } // This code is contributed by Rajput-Ji
Python3
# Python3 program to find highly totient numbers # Function to find euler totient number def phi(n): result = n; # Initialize result as n # Consider all prime factors of n and # subtract their multiples from result p = 2 while(p*p <= n): # Check if p is a prime factor. if (n % p == 0): # If yes, then update n and result while (n % p == 0): n //= p; result -= (result // p); p += 1 # If n has a prime factor greater than sqrt(n) # (There can be at-most one such prime factor) if (n > 1): result -= (result // n); return result; # Function to find first n highly totient numbers def Highly_Totient(n): # Count of Highly totient numbers # and value of count of phi of previous numbers count = 0 p_count = -1 # Store all the values of phi(x) upto # 10^5 with frequencies mp = dict() i = 1 while i < 100000: tmp = phi(i) if tmp not in mp: mp[tmp] = 0 mp[tmp] += 1; i += 1 i = 1 while (count < n): # If count is greater than count of # previous element if ((i in mp) and mp[i] > p_count): # Display the number print(i, end = ''); if(count < n - 1): print(", ", end = ''); # Store the value of phi p_count = mp[i]; count += 1 i += 1 # Driver code if __name__=='__main__': n = 20; # Function call Highly_Totient(n); # This code is contributed by rutvik_56
C#
// C# program to find highly totient numbers using System; using System.Collections.Generic; class GFG { // Function to find euler totient number static int phi(int n) { int result = n; // Initialize result as n // Consider all prime factors of n and // subtract their multiples from result for (int p = 2; p * p <= n; ++p) { // Check if p is a prime factor. if (n % p == 0) { // If yes, then update n and result while (n % p == 0) n /= p; result -= result / p; } } // If n has a prime factor greater than sqrt(n) // (There can be at-most one such prime factor) if (n > 1) result -= result / n; return result; } // Function to find first n highly totient numbers static void Highly_Totient(int n) { // Count of Highly totient numbers // and value of count of phi of // previous numbers int count = 0, p_count = -1, i; // Store all the values of phi(x) upto // 10^5 with frequencies Dictionary<int, int> mp = new Dictionary<int, int>(); for (i = 1; i < 100000; i++) { if(mp.ContainsKey(phi(i))) { mp[phi(i)] = mp[phi(i)] + 1; } else { mp.Add(phi(i), 1); } } i = 1; while (count < n) { // If count is greater than count of // previous element if (mp.ContainsKey(i)&&mp[i] > p_count) { // Display the number Console.Write(i); if(count < n - 1) Console.Write(", "); // Store the value of phi p_count = mp[i]; count++; } i++; } } // Driver code public static void Main(String[] args) { int n = 20; // Function call Highly_Totient(n); } } // This code is contributed by Rajput-Ji
Javascript
<script> // javascript program to find highly totient numbers // Function to find euler totient number function phi(n) { var result = n; // Initialize result as n // Consider all prime factors of n and // subtract their multiples from result for (var p = 2; p * p <= n; ++p) { // Check if p is a prime factor. if (n % p == 0) { // If yes, then update n and result while (n % p == 0) n /= p; result -= result / p; } } // If n has a prime factor greater than sqrt(n) // (There can be at-most one such prime factor) if (n > 1) result -= result / n; return result; } // Function to find first n highly totient numbers function Highly_Totient(n) { // Count of Highly totient numbers // and value of count of phi of previous numbers var count = 0, p_count = -1; // Store all the values of phi(x) upto // 10^5 with frequencies var mp = new Map(); for (i = 1; i < 100000; i++) { if (mp.has(phi(i))) { mp.set(phi(i), mp.get(phi(i)) + 1); } else { mp.set(phi(i), 1); } } var i = 1; while (count < n) { // If count is greater than count of // previous element if (mp.has(i) && mp.get(i) > p_count) { // Display the number document.write(i); if (count < n - 1) document.write(", "); // Store the value of phi p_count = mp.get(i); count++; } i++; } } // Driver code var n = 20; // Function call Highly_Totient(n); // This code is contributed by gauravrajput1 </script>
Producción:
1, 2, 4, 8, 12, 24, 48, 72, 144, 240, 432, 480, 576, 720, 1152, 1440, 2880, 4320, 5760, 8640
Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. [Como O(N) > O(sqrt(N)*logN), ya que usamos bucles anidados para atravesar sqrt(N)*logN veces]
Espacio auxiliar: O(100000), ya que estamos usando espacio extra para el mapa.
Este método no se puede utilizar para encontrar más de 1000 Número de pacientes altamente.
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA