¿Cuántos números en un rango dado son coprimos a N?

Question

Hay un buen algoritmo para el cálculo de los números de $x$ $A$ $B$ $x$ $N$ coprime? Esto es igual a esta pregunta , excepto para el rango.

La factorización de $N$ es conocido. Yo en realidad necesidad de resolver el problema por solucionado $N$ y muchos rangos, así que creo que me puede marcar todos los múltiplos de factores de $N$ BitSet y simplemente contar lo que queda. Pero hay una mejor solución (o uno para el caso de necesito la respuesta para un solo rango)?

Answer 1

Deje $f(C)$ el número de enteros de $1$ $C$que son relativamente primos a $N$. Si podemos calcular $f(C)$, el resto es fácil. Dicen que nos están permitiendo $A \le x\le B$. A continuación, nuestra respuesta es $f(B)-f(A-1)$.

Tenga en cuenta que $f(C)$ $C$ menos el número de enteros en el intervalo de $[1,C]$ que no relativamente primer a $N$.

Llame a este número $g(C)$. Por lo $f(C)=C-g(C)$. Atacamos el problema de encontrar $g(C)$.

Si $N$ es una fuente primaria de energía $p^a$, es fácil. Los números en el intervalo de $[1,C]$ que no relativamente primer a $N$ son los múltiplos de $p$. Así $$g(C)=\left\lfloor \frac{C}{p}\right\rfloor,$$ donde$\lfloor x\rfloor$, es habitual el "piso" de la función.

Si $N$ tiene la primera energía de la factorización de la $p^aq^b$ donde $p$ $q$ son distintos de los números primos, a continuación, $g(C)$ es el número de enteros en $[1,C]$ que son divisibles por $p$ o $q$ o ambos. Por medio de la Inclusión/Exclusión, obtenemos $$g(C)=\left\lfloor \frac{C}{p}\right\rfloor+\left\lfloor \frac{C}{q}\right\rfloor-\left\lfloor \frac{C}{pq}\right\rfloor.$$ La razón es que cuando sumamos los dos primeros términos anteriores, estamos contando dos veces todos los múltiplos de $pq$.

Si $N$ tiene la primera energía de la factorización de la $p^aq^br^c$, la misma idea básica de las obras. Tenemos $$g(C)=\left\lfloor \frac{C}{p}\right\rfloor+\left\lfloor \frac{C}{q}\right\rfloor+\left\lfloor \frac{C}{r}\right\rfloor-\left\lfloor \frac{C}{qr}\right\rfloor -\left\lfloor \frac{C}{pr}\right\rfloor-\left\lfloor \frac{C}{pq}\right\rfloor+\left\lfloor \frac{C}{pqr}\right\rfloor.$$

Expresiones similares de trabajo para $N$ que es más complicado en el primer poder de la factorización.

Nota: Dependiendo de los tamaños relativos de $A$, $B$, y $N$, hay accesos directos disponibles, la participación de Euler $\varphi$-función. Esto es porque hay $\varphi(N)$ números primos relativos a $N$ en el intervalo de $[kN+1,(k+1)N]$. Como usted sabe, el primer poder de la factorización de $N$, $\varphi(N)$ está dada por una fórmula simple. Por lo tanto nuestro problema se resuelve si podemos encontrar a $f(D)$$D\lt N$. Para dividiendo $C$ $N$ nos da el número de los "trozos" de forma $[kN+1,(k+1)N]$ hay $C$. Estos son tratados con el uso de la $\varphi$-función, y el resto $D$ es tratado por la Inclusión/Exclusión.

Y además de los hechos matemáticos, uno necesita ideas de programación para producir una solución eficiente.