Generar todos los pares de coprimos dentro de límites

Question

Digo que quiero generar todos los pares coprimos ($a,b$) donde no $a$ $A$ es superior y no supera el $b$ $B$.

¿Hay una manera eficiente de hacer esto?

Answer 1

Si $A$ $B$ son comparables en valor, el algoritmo para la generación de la secuencia de Farey puede adaptarse bien; genera todos los pares de coprime enteros $(a,b)$$1\leq a<b\leq N$, con una constante de los requisitos de memoria y $O(1)$ operaciones por par de salida. Se ejecuta con $N=\max(A,B)$ y el filtrado de pares cuyos otro componente excede el otro obligado produce todos los coprime parejas que buscan.

Si los valores de $A$ $B$ difieren demasiado, el tiempo perdido en el filtrado de la irrelevante pares sería demasiado alto y un enfoque diferente (como las propuestas por Thomas Andrews) podría ser necesaria.

Answer 2

En general, si $(a,b)$ es coprimo $(a-b,b)$ son coprimos y $(a,b-a)$ son coprimos. Lo que puedes hacer esto por inducción, que tendrá tiempo de $O(AB)$ y $O(AB)$ memoria.

No se puede hacer en mejor momento, ya que hay salidas de $O(AB)$ - % grande $A,B$, se trata de $\frac{6AB}{\pi^2}$ salidas. Posiblemente lo puedes hacer en la memoria mejor - mantener todos los valores más pequeños es un costo.