Algoritma untuk memeriksa apakah daftar bilangan bulat adalah koprime berpasangan

Apakah ada algoritma yang efisien untuk memeriksa apakah daftar bilangan bulat adalah koprime berpasangan, atau akankah algoritma yang lebih umum menjadi pilihan terbaik yang tersedia?

algorithms primes pengguna2782067
sumber

Hanya untuk memastikan, maksud Anda bahwa setiap pasangan bilangan bulat di set Anda adalah coprime?

Draconis

ya, setiap kombinasi dari 2 bilangan bulat harus

koprime

Jawaban:

Pertama, dua fakta tentang bilangan bulat koprime:

Iff $a$ dan $b$ lalu coprime $ab = \mathrm{lcm}(a,b)$
Iff $a$ adalah koprime bagi keduanya $b$ dan $c$ , kemudian $a$ adalah hak untuk $bc$

Ini mengikuti dari ini bahwa satu set bilangan bulat yang berbeda $\{a, b, \cdots z\}$ adalah pasangan berpasangan jika produknya sama dengan kelipatan paling tidak umum.

Anda dapat menghitung multiple yang paling tidak umum dengan menggunakan identitas berikut:

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))$

Dengan asumsi Anda punya $n$ angka dengan $k$ masing-masing digit, dan mengalikan / membagi / modding dua angka adalah $O(1)$ (yang mungkin atau mungkin bukan asumsi yang baik tergantung pada model Anda), maka:

Menghitung produk set Anda $O(n)$
Menghitung gcd dari dua angka dibutuhkan $O(k)$
Menghitung lcm dari dua angka juga perlu dilakukan $O(k)$ , dengan mengurangi ke gcd
Jadi menghitung lcm dari seluruh set Anda $O(nk)$

Dengan demikian, kompleksitas waktu dari keseluruhan algoritma adalah $O(nk)$ .

Draconis
sumber

Jika OP benar-benar menerapkan ini, mungkin ada baiknya untuk mengevaluasi apakah produk / lcm sama untuk setiap angka ketika dibaca daripada setelah mengalikan semua / lcm semuanya. Ini tidak akan mengubah kerumitan tetapi jika Anda mengharapkan sebagian besar daftar tidak menjadi koprime (seperti halnya daftar panjang angka acak) maka kemungkinan besar akan lebih cepat

sudo rm -rf slash

@ WD Saya percaya intinya adalah bahwa dengan menguji secara bertahap, Anda dapat memberikan jaminan lebih awal begitu contoh non-coprime pertama ditemukan, yang bertentangan hanya setelah memproses seluruh daftar. Karena kami berharap sebagian besar daftar tidak berpasangan berpasangan dan kami tidak memiliki informasi tentang daftar yang diuji, kami harus berharap bahwa daftar itu mungkin bukan berpasangan berpasangan, dan karenanya melanjutkan dengan prosedur yang dioptimalkan untuk kasus umum .

Andrea Reina

@AndreaReina terima kasih karena telah menulisnya dengan lebih jelas

sudo rm -rf slash

Catatan implementasi lain ... Menggunakan gcd == 1 bukannya lcm == prod mungkin lebih mudah karena sejauh yang saya tahu algos lcm terbaik menggunakan gcd

sudo rm -rf slash

Jika Anda menghitung jumlah digit angka, tidak masuk akal untuk menganggap bahwa perkalian dan pembagian adalah

O (1)

$O(1)$ . Mereka

Ω (k^{a})

$\Omega(k^a)$ untuk beberapa

k > 1

$k \gt 1$ .

Gilles 'SANGAT berhenti menjadi jahat'

Iya. Pendekatan naif untuk memeriksa setiap pasangan angka membutuhkan waktu kuadratik, tetapi ada algoritma yang lebih efisien. Ada algoritma waktu yang hampir linier, dijelaskan dalam makalah berikut:

Daniel J. Bernstein. Anjak menjadi coprim pada dasarnya waktu linear . Jurnal Algoritma 54 (2005), 1--30.

Lihat juga https://cstheory.stackexchange.com/q/3393/5038 . Itu hampir seefisien yang mungkin Anda harapkan.

Untuk memperjelas bagaimana ini membantu situasi Anda, setelah Anda menemukan basis koprime dan memfaktorkan masing-masing elemen atas dasar, sepele untuk memeriksa apakah mereka adalah pasangan berpasangan: jika mereka bukan pasangan berpasangan, maka beberapa pasangan akan memiliki kesamaan faktor, dan itu akan menjadi faktor yang ada dalam basis coprime dan yang hadir dalam faktorisasi keduanya. Jika tidak ada faktor yang umum muncul dalam faktorisasi dua atau lebih angka, maka Anda tahu angka-angka tersebut adalah pasangan berpasangan. Setelah Anda memiliki faktorisasi, mudah untuk memeriksa dalam waktu linier apakah ada angka di lebih dari satu faktorisasi.

DW
sumber

Saya tidak melihat bagaimana Factoring over a coprime basehubungannya dengan checking if a list of integers is pairwise coprime(belum).

greybeard

@ Greybeard, lihat jawaban yang diedit - Saya menambahkan paragraf di akhir menjelaskan.

Temukan faktor prima dari setiap angka. Angka-angka semua koprime berpasangan jika dan hanya jika setiap prime dalam seluruh koleksi berbeda. Pemeriksaan ini dapat dilakukan dalam waktu O (n) menggunakan tabel hash.

Sunting: Jawaban Draconis lebih baik, karena tidak memerlukan faktorisasi. Perhitungan GCD lebih cepat jika angka Anda besar dan / atau prima.

MackTuesday
sumber

Anjak sangat lambat. Sejauh yang kami tahu, tidak ada algoritma yang efisien untuk anjak piutang - dan kami tentu saja tidak tahu satu yang membutuhkan waktu O (n). Pada dasarnya, algoritma ini akan mendekati waktu eksponensial (secara teknis, waktu subeksponensial tetapi superpolinomial).