Pengujian Keprimaan hingga sqrt(n)
Memeriksa satu angka secara efisien
Pengujian Keprimaan hingga sqrt(n) adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 2 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 Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Pertanyaan tentang Bilangan Prima
Salah satu keterampilan dasar matematika adalah menentukan apakah sebuah bilangan merupakan bilangan prima. Bilangan prima memiliki tepat dua pembagi: satu dan dirinya sendiri. Mari kita mengujinya dengan cepat. 🔍
Pemeriksaan Naif
Anda dapat mencoba membagi n dengan setiap bilangan dari 2 hingga n dikurangi 1. Cara ini benar, tetapi sangat lambat saat n besar.
Trik Akar Kuadrat
Inilah wawasan utamanya: Anda hanya perlu menguji pembagi hingga akar kuadrat n. Setelah itu, tidak ada faktor baru yang dapat muncul.
Mengapa Akar Kuadrat Sudah Cukup
Pembagi muncul dalam pasangan yang hasil kalinya sama dengan n. Jika keduanya lebih besar dari akar kuadrat, hasil kali keduanya akan melebihi n, dan itu mustahil.
Batas Perulangan
Ulangi i mulai dari 2 selama i kali i tetap kurang dari atau sama dengan n. Menggunakan i*i menghindari kesalahan bilangan pecahan dari sqrt pada bilangan bulat besar.
while i * i <= n:
...Tangani Kasus Kecil
Bilangan di bawah 2 tidak pernah prima, jadi tolak sejak awal. Pemeriksaan awal ini menjaga perulangan utama tetap bersih dan benar.
if n < 2:
return FalseFungsi Lengkap
Gabungkan semuanya: lakukan pemeriksaan awal terhadap nilai kecil, lalu telusuri kemungkinan pembagi hingga akar. Pembagian tanpa sisa berarti n bersifat komposit.
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return TruePercepat Prosesnya
Periksa 2 secara terpisah, lalu uji hanya bilangan ganjil. Melewati bilangan genap kira-kira membagi dua pekerjaan tanpa menambah kompleksitas.
if n % 2 == 0:
return n == 2Biaya Waktu
Pengujian ini berjalan dalam waktu O(sqrt n). Untuk satu bilangan hingga satu miliar, proses ini hanya memerlukan sekitar 30.000 operasi sederhana.
Satu Bilangan, Bukan Banyak
Pengujian akar kuadrat sangat cocok untuk satu atau beberapa kueri. Jika Anda memerlukan pengujian keprimaan untuk seluruh rentang, saringan akan jauh lebih cepat.
Hindari Masalah Akar Kuadrat
Membandingkan dengan i*i, bukan math.sqrt, menghindari kesalahan pembulatan yang dapat keliru menerima atau menolak bilangan yang berada di ambang batas.
Pemeriksaan Cepat
Pastikan kembali batas yang membuat pengujian ini cepat.
Ringkasan
Sekarang Anda dapat menguji keprimaan satu bilangan dalam waktu O(sqrt n), melakukan pemeriksaan awal terhadap nilai kecil, melewati bilangan genap, dan menggunakan i*i agar tetap akurat. ✅
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pengujian Keprimaan hingga sqrt(n)” gratis?
Ya — teks lengkap “Pengujian Keprimaan hingga sqrt(n)” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Pengujian Keprimaan hingga sqrt(n)”?
Memeriksa satu angka secara efisien Kamu berlatih Competitive Programming Academy 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 Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy 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 2 dari 4.
Berapa lama pelajaran “Pengujian Keprimaan hingga sqrt(n)” 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 Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy 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