Algoritmo para verificar si una lista de enteros es coprime por pares

¿Existen algoritmos eficientes para verificar si una lista de enteros es coprime por pares, o sería un algoritmo más general la mejor opción disponible?

algorithms primes usuario2782067
fuente

Solo para asegurarse, ¿quiere decir que cada par de enteros en su conjunto es coprime?

Draconis

sí, cada combinación de 2 enteros debe ser coprime

user2782067

Respuestas:

Primero, dos hechos sobre enteros coprimos:

Iff y son primos entre sí, entonces $a$ $b$ $ab = \mathrm{lcm}(a,b)$
Si es coprimo para y , entonces es coprimo para $a$ $b$ $c$ $a$ $bc$

De esto se deduce que un conjunto de enteros distintos es coprimo en pares si su producto es igual a su mínimo común múltiplo. $\{a, b, \cdots z\}$

Puede calcular el mínimo común múltiplo utilizando la siguiente identidad:

l c m (a, b, c) = l c m (a, l c m (b, c))

$\mathrm{lcm}(a,b,c) = \mathrm{lcm}(a,\mathrm{lcm}(b,c))$

Suponiendo que tiene números con dígitos cada uno, y multiplicando / dividiendo / modificando dos números es (que puede ser o no una buena suposición dependiendo de su modelo), entonces: $n$ $k$ $O(1)$

Calcular el producto de su conjunto toma $O(n)$
Calcular el mcd de dos números toma $O(k)$
Calcular el mcm de dos números también toma , por reducción a mcd $O(k)$
Entonces calcular el mcm de todo tu conjunto toma $O(nk)$

Por lo tanto, la complejidad temporal de todo el algoritmo es . $O(nk)$

Draconis
fuente

Si OP realmente está implementando esto, puede valer la pena evaluar si el producto / mcm es igual para cada número a medida que se leen, en lugar de multiplicarlos todos / mcm a todos. Esto no cambiará la complejidad, pero si espera que la mayoría de las listas no sean coprimes (como sería el caso de una larga lista de números aleatorios), lo más probable es que sea más rápido

sudo rm -rf slash

@DW Creo que el punto es que al realizar pruebas incrementales, puede rescatar anticipadamente una vez que se encuentra el primer ejemplo no coprime, en lugar de solo después de procesar toda la lista. Dado que esperamos que la mayoría de las listas no sean coprime por pares y no tenemos ninguna información sobre la lista que se está probando, deberíamos esperar que la lista probablemente no sea coprime por pares y, por lo tanto, proceder con un procedimiento optimizado para ese caso común .

Andrea Reina

@AndreaReina exactamente gracias por escribirlo más claramente

sudo rm -rf slash

Otra nota de implementación ... Usar gcd == 1 en lugar de lcm == prod es probablemente más fácil ya que hasta donde yo sé, los mejores algos lcm usan el gcd de todos modos

sudo rm -rf slash

Si cuenta el número de dígitos de los números, no tiene sentido suponer que la multiplicación y la división son . Son para algunos .

O (1)

$O(1)$

Ω (k^{a})

$\Omega(k^a)$

k > 1

$k \gt 1$

Gilles 'SO- deja de ser malvado'

Si. El enfoque ingenuo de verificar cada par de números lleva tiempo cuadrático, pero hay algoritmos más eficientes. Existe un algoritmo de tiempo casi lineal, descrito en el siguiente documento:

Daniel J. Bernstein. Factorizando en coprimos en un tiempo esencialmente lineal . Journal of Algorithms 54 (2005), 1--30.

Consulte también https://cstheory.stackexchange.com/q/3393/5038 . Eso es casi tan eficiente como podrías esperar.

Para aclarar cómo esto ayuda con su situación, una vez que haya encontrado una base coprime y haya factorizado cada elemento sobre la base, es trivial verificar si son coprime por pares: si no son coprime por pares, algún par tendrá un común factor, y ese será un factor que está en la base coprime y que está presente en la factorización de ambos. Si no hay un factor común en la factorización de dos o más números, entonces sabrá que los números son coprimos por pares. Una vez que tenga las factorizaciones, es fácil verificar en tiempo lineal si hay números en más de una factorización.

DW
fuente

No veo cómo se Factoring over a coprime baserelaciona con checking if a list of integers is pairwise coprime(todavía).

barba gris

@greybeard, vea la respuesta editada: agregué un párrafo al final explicando.

Encuentra los factores primos de cada número. Todos los números son primos pares por pares si y solo si cada primo en toda la colección es distinto. Esta verificación se puede hacer en tiempo O (n) usando una tabla hash.

Editar: la respuesta de Draconis es mejor, porque no requiere ninguna factorización. El cálculo de GCD es más rápido si sus números son grandes y / o primos.

Mack martes
fuente

Factoring es muy lento. Hasta donde sabemos, no existe un algoritmo eficiente para la factorización, y ciertamente no conocemos uno que tome tiempo O (n). Básicamente, este algoritmo estará cerca del tiempo exponencial (técnicamente, tiempo subexponencial pero superpolinómico).