Algorithme pour vérifier si une liste d'entiers est un coprime par paire

Existe-t-il des algorithmes efficaces pour vérifier si une liste d'entiers est coprime par paire, ou un algorithme plus général serait-il la meilleure option disponible?

algorithms primes user2782067
la source

Juste pour être sûr, vous voulez dire que chaque paire d'entiers de votre ensemble est coprime?

Draconis

oui, chaque combinaison de 2 nombres entiers doit être coprime

user2782067

Réponses:

Tout d'abord, deux faits sur les entiers premiers:

Iff $a$ et $b$ sont coprime, alors $ab = \mathrm{lcm}(a,b)$
Iff $a$ est coprime pour les deux $b$ et $c$ , puis $a$ est coprime à $bc$

Il en résulte qu'un ensemble d'entiers distincts $\{a, b, \cdots z\}$ est un coprime par paire si son produit est égal à son multiple le moins commun.

Vous pouvez calculer le multiple le moins commun en utilisant l'identité suivante:

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

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

En supposant que vous ayez $n$ numéros avec $k$ chiffres chacun, et multiplier / diviser / modifier deux nombres est $O(1)$ (qui peut ou non être une bonne hypothèse selon votre modèle), alors:

Le calcul du produit de votre set prend $O(n)$
Le calcul du pgcd de deux nombres prend $O(k)$
Le calcul du ppcm de deux nombres prend donc aussi $O(k)$ , par réduction en pgcd
Donc, calculer le lcm de votre ensemble prend $O(nk)$

Ainsi, la complexité temporelle de l'ensemble de l'algorithme est $O(nk)$ .

Draconis
la source

Si OP le met réellement en œuvre, il peut être utile d'évaluer si les produits / lcm sont égaux pour chaque nombre au fur et à mesure qu'ils sont lus plutôt qu'après les avoir tous multipliés / lcm-ing tous. Cela ne changera pas la complexité mais si vous vous attendez à ce que la plupart des listes ne soient pas coprimes (comme ce serait le cas pour une longue liste de nombres aléatoires), alors ce sera probablement plus rapide

sudo rm -rf slash

@DW Je pense que le fait est qu'en testant de manière incrémentielle, vous pouvez libérer sous caution une fois le premier exemple non coprime trouvé, par opposition à seulement après avoir traité la liste entière. Étant donné que nous nous attendons à ce que la plupart des listes ne soient pas coprime par paire et que nous ne disposions d'aucune information sur la liste en cours de test, nous devons nous attendre à ce que la liste ne soit probablement pas coprime par paire, et donc procéder à une procédure optimisée pour ce cas commun .

Andrea Reina

@AndreaReina merci beaucoup de l'avoir écrit plus clairement

sudo rm -rf slash

Une autre note d'implémentation ... Utiliser gcd == 1 au lieu de lcm == prod est probablement plus facile car pour autant que je sache, les meilleurs algos lcm utilisent le gcd de toute façon

sudo rm -rf slash

Si vous comptez le nombre de chiffres des nombres, cela n'a aucun sens de supposer que la multiplication et la division sont

O (1)

$O(1)$ . Ils sont

Ω (k^{a})

$\Omega(k^a)$ pour certains

k > 1

$k \gt 1$ .

Gilles 'SO- arrête d'être méchant'

Oui. L'approche naïve de la vérification de chaque paire de nombres prend du temps quadratique, mais il existe des algorithmes plus efficaces. Il existe un algorithme de temps presque linéaire, décrit dans l'article suivant:

Daniel J. Bernstein. Factorisation des coprimes en temps essentiellement linéaire . Journal of Algorithms 54 (2005), 1--30.

Voir également https://cstheory.stackexchange.com/q/3393/5038 . C'est presque aussi efficace que vous pourriez l'espérer.

Pour clarifier comment cela aide à votre situation, une fois que vous avez trouvé une base de coprime et factorisé chaque élément sur la base, il est trivial de vérifier s'ils sont coprime par paire: s'ils ne sont pas coprime par paire, alors une paire aura un commun facteur, et ce sera un facteur qui est dans la base du coprime et qui est présent dans la factorisation des deux. S'il n'y a aucun facteur commun à présenter dans la factorisation de deux nombres ou plus, alors vous savez que les nombres sont des nombres premiers par paire. Une fois que vous avez les factorisations, il est facile de vérifier en temps linéaire s'il y a des nombres dans plus d'une factorisation.

DW
la source

Je ne vois pas comment (encore) se Factoring over a coprime baserapporte à checking if a list of integers is pairwise coprime.

greybeard

@greybeard, voir la réponse modifiée - j'ai ajouté un paragraphe à la fin expliquant.

Trouvez les facteurs premiers de chaque nombre. Les nombres sont tous des nombres premiers par paire si et seulement si chaque nombre premier de la collection entière est distinct. Cette vérification peut être effectuée en temps O (n) à l'aide d'une table de hachage.

Edit: la réponse de Draconis est meilleure, car elle ne nécessite aucune factorisation. Le calcul GCD est plus rapide si vos nombres sont grands et / ou premiers.

MackTuesday
la source

L'affacturage est très lent. À notre connaissance, il n'existe pas d'algorithme efficace pour la factorisation - et nous n'en connaissons certainement pas un qui prend du temps O (n). Fondamentalement, cet algorithme sera proche du temps exponentiel (techniquement, temps subexponentiel mais superpolynomial).