GCD, LCM & Algoritma Euclid
Menghitung pembagi dengan cepat dan tepat
GCD, LCM & Algoritma Euclid adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Mengapa Pembagi Penting
Begitu banyak soal pemrograman kompetitif bergantung pada faktor persekutuan dari dua bilangan. Alat yang paling berguna di sini adalah GCD, yaitu pembagi persekutuan terbesar. 🔢
Makna GCD
GCD dari dua bilangan bulat adalah bilangan terbesar yang membagi keduanya tanpa sisa. Untuk 12 dan 18, nilainya adalah 6 karena 6 membagi keduanya dengan tepat.
Cara Lambat
Anda dapat menguji setiap bilangan mulai dari nilai yang lebih kecil secara menurun sampai menemukan bilangan yang membagi keduanya. Cara ini berhasil, tetapi terlalu lambat untuk input besar.
Wawasan Euklides
Algoritma Euklides adalah cara yang cepat. Gagasan utamanya: GCD dari a dan b sama dengan GCD dari b dan sisa pembagian a oleh b.
Relasi Rekurensi
Ulangi langkah pertukaran dan modulo sampai sisanya menjadi nol. Nilai tak nol terakhir yang tersisa adalah jawaban Anda, yaitu GCD itu sendiri.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aBuat Kodenya Sendiri
Sebuah perulangan singkat terus mengganti pasangan tersebut sampai b mencapai nol. Proses ini berjalan dalam sekitar logaritma langkah, sangat cepat bahkan untuk bilangan yang sangat besar.
def gcd(a, b):
while b:
a, b = b, a % b
return aGunakan Pustaka Standar
Anda hampir tidak pernah perlu membuatnya dari awal. Python menyediakan math.gcd, yang benar, cepat, dan menangani argumen nol untuk Anda.
from math import gcd
print(gcd(12, 18))Dari GCD ke LCM
LCM, yaitu kelipatan persekutuan terkecil, adalah bilangan terkecil yang habis dibagi oleh kedua nilai tersebut. Konsep ini terhubung langsung dengan GCD yang baru saja Anda hitung.
Rumus LCM
Kalikan kedua bilangan, lalu bagi dengan GCD-nya. Selalu lakukan pembagian terlebih dahulu untuk menghindari luapan pada hasil kali yang sangat besar.
def lcm(a, b):
return a // gcd(a, b) * bGCD pada Seluruh Daftar
Untuk menerapkan GCD pada banyak bilangan, hitung secara berpasangan dan berantai. Python menggunakan reduksi untuk menerapkan math.gcd dari kiri ke kanan pada daftar.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)Tangani Kasus Nol
Menurut definisi, gcd(a, 0) sama dengan a, dan gcd(0, 0) adalah 0. Mengetahui kasus batas ini mencegah perulangan Anda berperilaku keliru saat menerima input kosong.
Pemeriksaan Cepat
Saatnya memastikan langkah inti Euklides.
Ringkasan
Sekarang Anda dapat menghitung GCD dengan algoritma Euklides dalam langkah logaritmik, menurunkan LCM darinya, dan menerapkan keduanya pada seluruh daftar. ✅
Pertanyaan yang Sering Diajukan
Apakah pelajaran “GCD, LCM & Algoritma Euclid” gratis?
Ya — teks lengkap “GCD, LCM & Algoritma Euclid” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “GCD, LCM & Algoritma Euclid”?
Menghitung pembagi dengan cepat dan tepat Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “GCD, LCM & Algoritma Euclid” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- GCD, LCM & Algoritma Euclid
- Pengujian Keprimaan hingga sqrt(n)
- Saringan Eratosthenes
- Faktorisasi Prima & Pembagi