Algoritme for at kontrollere, om en liste over heltal er parvis coprime

user2782067 06/12/2018. 3 answers, 467 views
algorithms primes

Er der nogen effektive algoritmer til at kontrollere, om en liste over heltal er parvis coprime, eller ville en mere generel algoritme være den bedste løsning til rådighed?

3 Answers


Draconis 06/12/2018.

For det første to fakta om coprime heltall:

  • Iff $ a $ og $ b $ er coprime, derefter $ ab = \ mathrm {lcm} (a, b) $
  • Iff $ a $ er coprime til både $ b $ og $ c $, så $ a $ er coprime til $ bc $

Det følger heraf, at et sæt særskilte heltal $ \ {a, b, \ cdots z \} $ er parvis kopi, hvis dets produkt er lig med dets mindst almindelige multiple.

Du kan beregne det mindst almindelige multiple ved at bruge følgende identitet:

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

Forudsat at du har $ n $ tal med $ k $ cifre hver og multiplicere / dividere / modding er to tal $ O (1) $ (hvilket måske er en god antagelse afhængigt af din model), så:

  • Beregning af produktet af dit sæt tager $ O (n) $
  • Beregning af gcd på to tal tager $ O (k) $
  • Beregning af lcm af to tal tager således også $ O (k) $, ved reduktion til gcd
  • Så beregning af lcm af hele dit sæt tager $ O (nk) $

Således er tidskompleksiteten af ​​hele algoritmen $ O (nk) $.


D.W. 06/13/2018.

Ja. Den naive tilgang til kontrol af hvert par tal tager kvadratisk tid, men der er mere effektive algoritmer. Der er en næsten lineær tidsalgoritme, der beskrives i det følgende papir:

Daniel J. Bernstein. Factoring i coprimes i hovedsagelig lineær tid . Journal of Algorithms 54 (2005), 1-30.

Se også https://cstheory.stackexchange.com/q/3393/5038 . Det er næsten lige så effektivt, som du måske kunne håbe på.

For at klarlægge, hvordan dette hjælper med din situation, når du først har fundet et coprime-grundlag og fakturerede hvert element over basen, er det trivielt at tjekke, om de er parret coprime: hvis de ikke er parvise coprime, vil nogle par få en fælles faktor, og det vil være en faktor, der er på coprime basis, og som er til stede i faktoriseringen af ​​begge. Hvis der ikke er nogen faktor, der er almindelig at præsentere i faktoriseringen af ​​to eller flere tal, så ved du, at tallene er parvis kopi. Når du har faktoriseringerne, er det nemt at kontrollere lineær tid, om der er tal i mere end en faktorisering.


MackTuesday 06/13/2018.

Find de primære faktorer i hvert nummer. Tallene er alle parvise coprime hvis og kun hvis hver primer i hele samlingen er forskellig. Denne check kan udføres i O (n) tid med et hashbord.

Rediger: Draconis 'svar er dog bedre, fordi det ikke kræver nogen faktorisering. GCD beregning er hurtigere, hvis dine tal er store og / eller primære.

Related questions

Hot questions

Language

Popular Tags