Es posible, pero poco probable, que esté preguntando sobre el cálculo del valor del paciente para un valor. En ese caso, queremos los factores del número, lo que generalmente significa que usamos un método rápido de factorización de propósito general (generalmente algoritmos múltiples; este es otro tema). La única forma en que un tamiz entra aquí es si está haciendo la división de prueba como su método de factorización y desea usar un tamiz para obtener primos. En ese momento, se ha desviado del tema principal y ha entrado en “¿cómo mejor tamizo los primos?”, Donde la respuesta es típicamente “Tamiz segmentado de Eratóstenes”, ya que sigue siendo el método más rápido en la práctica.
Sin embargo, especialmente si el Proyecto Euler es lo tuyo, estás preguntando cómo calcular todos los clientes en un rango, por ejemplo, todos phi (i) para 0 <i <n, entonces definitivamente estamos en el camino correcto. Podemos usar un tamiz para hacer esto mucho más rápido que calcular individualmente el total de cada valor. Cambia el problema de "para cada número entero menor que n, encuentre los divisores del número" a "para cada número primo, encuentre todos los múltiplos primos menores que n", que es mucho más rápido.
Hacer búsquedas en Google muestra una serie de implementaciones y debates. Por ejemplo, ¿Cómo calcular estas sumas de suma total eficientemente?
- ¿Por qué es importante la teoría del tipo de homotopía?
- ¿Hay una manera eficiente de comparar la similitud de una cadena con cada permutación de otra cadena (es decir, un grupo simétrico)?
- ¿Qué son los códigos ponderados y no ponderados?
- Dado un número X, encuentre el siguiente número con el mismo número de 1 bits en su representación binaria. Para la entrada x = 12, ¿la salida sería 17?
- ¿Están algunas de las máquinas en 'On Computable Numbers' (A. Turing 1936) buggy?
Para implementaciones, el tutorial en la función Totient de Euler para todos los números menores o iguales a n – GeeksforGeeks no es tan malo. El código es simple y no requiere espacio adicional. Mi código en danaj / Math-Prime-Util es aproximadamente 20 veces más rápido (phi (n) para todos n hasta 200 millones en 2.6s vs. 55s). Ambos son más rápidos que factorizar individualmente cada número hasta 200 millones (aunque a los 2.5 minutos no es horrible; sin embargo, la tasa de crecimiento es demoledora, ya que hasta 20M solo tomó 10 segundos).
