Interesante problema! A veces, los algoritmos de fuerza bruta son más seguros si es factible.
En este caso, supongamos que el rango dado es [a, b] es sensato y el número es n. Queremos encontrar todos los coprimos de n dentro de [a, b]. Ahora, una solución directa sería iterar sobre todo k, de modo que a <= k <= b y, determinar si k y n son coprimos. Dos números xey son coprimos si su máximo común divisor (MCD) es 1. Podemos calcular MCD usando el método de Euclides que tiene una complejidad de tiempo logarítmico.
Otra forma podría ser utilizar la factorización prima. Primero generamos la factorización prima de todos los números, k en [a, b]. Entonces dado n, también lo factorizamos. Ahora el problema se reduce a encontrar todos los números k donde no hay primo común entre k y n. En realidad no necesitamos el poder de cada primo dentro de la factorización prima; solo necesitamos los números primos. La búsqueda sigue siendo lineal, pero podemos acelerarla utilizando alguna función hash. Este método es más aplicable cuando tenemos un montón de n y el rango es fijo. Como paso previo al proceso, calculamos la factorización prima de todos los números en el rango dado y los almacenamos en una estructura de datos.
- ¿Cuál es la historia del aprendizaje automático?
- ¿Cómo se puede crear una aplicación gratis?
- ¿Cuáles son los pros y los contras en el arranque dual de mi computadora portátil Windows de alta gama con Ubuntu 14.04 en lo que respecta al rendimiento de mi computadora portátil con Windows?
- ¿Qué puedo hacer con Cloud Computing?
- ¿Resolver una versión restringida de un problema NP-completo en tiempo polinómico implica que todos los problemas NP-completos, cuando se restringen a esa versión, pueden resolverse en tiempo polinomial?
