Greatest Common Divisor

Q: Berapa kompleksitas waktu algoritma Euclid?

O(log(min(a, b))) langkah dan penggunaan ruang O(1) . Input paling lambat adalah bilangan Fibonacci berurutan: 701408733 dan 433494437 memerlukan 42 langkah, atau 43 jika bilangan yang lebih kecil diletakkan lebih dulu, jumlah terbanyak untuk pasangan apa pun hingga 10^9 .

Q: Berapa gcd dari dua bilangan yang relatif prima?

Yaitu 1 : dua bilangan saling prima tepat ketika keduanya tidak memiliki faktor prima yang sama. Dua bilangan prima yang berbeda selalu saling prima, begitu juga dua bilangan bulat berurutan seperti 8 dan 9 .

PemulaMatematika dan simulasi

+10

Kamu mendapatkan dua bilangan bulat positif a dan b. Kembalikan faktor persekutuan terbesar keduanya: bilangan bulat terbesar yang membagi keduanya tanpa sisa.

Contohnya, bilangan yang membagi 8 dan 12 adalah 1, 2, dan 4, jadi jawabannya adalah 4.

Fungsi

gcd(a: integer, b: integer) → integer

ainteger: bilangan bulat positif pertama
binteger: bilangan bulat positif kedua
Mengembalikaninteger: bilangan bulat terbesar yang membagi a dan b

Batasan

1 ≤ a ≤ 10⁹
1 ≤ b ≤ 10⁹

Contoh

Input: a = 12b = 18
Output: 6
Penjelasan: Faktor dari 12 adalah 1, 2, 3, 4, 6 dan 12; faktor dari 18 adalah 1, 2, 3, 6, 9 dan 18. Faktor terbesar yang ada di kedua daftar adalah 6.

Input: a = 17b = 5
Output: 1
Penjelasan: 17 dan 5 sama-sama bilangan prima dan berbeda, jadi satu-satunya pembagi yang mereka miliki bersama adalah 1.

Input: a = 42b = 42
Output: 42
Penjelasan: Suatu bilangan membagi dirinya sendiri, dan tidak ada bilangan yang lebih besar dari 42 yang dapat membagi 42, jadi faktor persekutuan terbesar dari 42 dan 42 adalah 42.

Pertanyaan lanjutan

Bisakah kamu memperluas algoritma Euclid agar juga mengembalikan bilangan bulat x dan y sehingga a × x + b × y = gcd(a, b)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Mencoba kandidat satu per satu bisa digunakan untuk angka kecil, tetapi dua angka yang mendekati 10^9 dan tidak memiliki faktor yang sama membutuhkan satu miliar percobaan. Aturan Euclid gcd(a, b) = gcd(b, a % b) mengurangi pasangan angka dengan begitu cepat sehingga tidak ada pasangan hingga 10^9 yang membutuhkan lebih dari 43 langkah.

Hitung mundur dari angka yang lebih kecil

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Tidak ada pembagi bersama yang lebih besar daripada bilangan yang lebih kecil. Mulai d dari min(a, b), lalu turunkan nilainya satu per satu sampai membagi keduanya. Karena kamu mulai dari angka terbesar, pembagi pertama yang ditemukan adalah yang terbesar, dan perulangan selalu berhenti paling lambat di 1. Untuk 12 dan 18, kamu mencoba dari 12 sampai 7, lalu berhenti di 6.

Biayanya satu percobaan untuk setiap kandidat. Untuk bilangan prima 999999937 dan 999999929, jawabannya adalah 1, jadi perulangan berjalan hampir 10^9 kali.

Algoritma

Tetapkan d ke nilai yang lebih kecil antara a dan b.
Selama a % d atau b % d tidak sama dengan 0, kurangi d sebanyak 1.
Kembalikan d.

def gcd(a, b):
    d = min(a, b)
    while a % d != 0 or b % d != 0:
        d -= 1
    return d

Algoritma Euclid

Intuisi

Tulis a = q × b + r dengan r = a % b. Bilangan yang membagi a dan b juga membagi r = a - q × b, dan bilangan yang membagi b dan r juga membagi a = q × b + r. Jadi, (a, b) dan (b, r) memiliki pembagi bersama yang sama, termasuk yang terbesar.

Ulangi hingga b bernilai 0. Setiap bilangan membagi 0, jadi gcd(a, 0) = a. Untuk 12 dan 18, pasangan bilangannya menjadi (12, 18), (18, 12), (12, 6), (6, 0), dan jawabannya adalah 6. Jika a lebih kecil, langkah pertama menukar posisi pasangan, jadi kamu tidak perlu mengurutkannya.

Setiap dua langkah setidaknya membagi dua bilangan yang lebih besar, jadi perulangan berjalan sebanyak O(log(min(a, b))) kali.

Algoritma

Selama b bukan 0, hitung r = a % b.
Tetapkan a = b dan b = r.
Saat b mencapai 0, kembalikan a.

def gcd(a, b):
    # gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a.
    while b != 0:
        a, b = b, a % b
    return a

Jebakan dan kasus tepi

Memperbarui dengan urutan yang salah. a = b diikuti b = a % b menghitung b % b, yang selalu bernilai 0. Simpan sisa pembagian terlebih dahulu, atau tetapkan keduanya sekaligus.
Mengembalikan b saat perulangan berakhir. Pada saat itu, b bernilai 0.
Menghentikan hitung mundur pada 2. Pasangan yang relatif prima seperti 17 dan 5 kemudian tidak menemukan jawaban.
Menggunakan pengurangan berulang alih-alih sisa pembagian. gcd(10^9, 1) kemudian memerlukan satu miliar pengurangan, sedangkan satu % menyelesaikan semuanya.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu algoritma Euclid?

O(log(min(a, b))) langkah dan penggunaan ruang O(1). Input paling lambat adalah bilangan Fibonacci berurutan: 701408733 dan 433494437 memerlukan 42 langkah, atau 43 jika bilangan yang lebih kecil diletakkan lebih dulu, jumlah terbanyak untuk pasangan apa pun hingga 10^9.

Apa perbedaan antara FPB dan KPK?

Faktor persekutuan terbesar adalah bilangan terbesar yang membagi kedua input; kelipatan persekutuan terkecil adalah bilangan terkecil yang habis dibagi oleh kedua input. Keduanya memiliki hubungan gcd(a, b) × lcm(a, b) = a × b, jadi lcm adalah a / gcd(a, b) × b.

Berapa gcd dari dua bilangan yang relatif prima?

Yaitu 1: dua bilangan saling prima tepat ketika keduanya tidak memiliki faktor prima yang sama. Dua bilangan prima yang berbeda selalu saling prima, begitu juga dua bilangan bulat berurutan seperti 8 dan 9.

def gcd(a, b):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

a = 12
b = 18

Output yang diharapkan