Pengujian Keprimaan hingga sqrt(n)

Satu kemahiran asas matematik ialah menentukan sama ada satu nombor ialah perdana. Nombor perdana mempunyai tepat dua pembahagi: satu dan dirinya sendiri. Mari kita mengujinya dengan pantas. 🔍

Anda boleh cuba membahagi n dengan setiap nombor dari 2 hingga n tolak 1. Cara ini betul, tetapi amat perlahan apabila n besar.

Inilah wawasan pentingnya: anda hanya perlu menguji pembahagi sehingga punca kuasa dua bagi n. Selepas itu, tiada faktor baharu boleh muncul.

Pembahagi datang dalam pasangan yang hasil darabnya ialah n. Jika kedua-duanya lebih besar daripada punca kuasa dua, hasil darabnya akan melebihi n, dan itu mustahil.

Ulang i dari 2 selagi i kali i kekal kurang daripada atau sama dengan n. Menggunakan i*i mengelakkan ralat titik apungan daripada sqrt bagi integer yang besar.

Nombor yang kurang daripada 2 tidak pernah perdana, jadi tolaknya dari awal. Pemeriksaan awal ini memastikan gelung utama anda bersih dan betul.

Gabungkan semuanya: lakukan pemeriksaan terhadap nilai kecil, kemudian imbas pembahagi yang mungkin sehingga punca kuasa dua. Sebarang pembahagian tepat bermaksud n ialah komposit.

Periksa 2 secara berasingan, kemudian uji nombor ganjil sahaja. Melangkau nombor genap kira-kira mengurangkan separuh kerja tanpa menambah kerumitan.

Ujian ini berjalan dalam masa O(sqrt n). Untuk satu nombor sehingga satu bilion, itu hanya kira-kira 30,000 operasi mudah.

Ujian punca kuasa dua sangat sesuai untuk satu atau beberapa pertanyaan. Jika anda memerlukan keperdanan bagi seluruh julat, penapis akan menjadi jauh lebih pantas.

Membandingkan dengan i*i dan bukannya math.sqrt mengelakkan ralat pembundaran yang boleh menyebabkan nombor pada sempadan diterima atau ditolak secara salah.

Anda kini boleh menguji keperdanan satu nombor dalam masa O(sqrt n), melakukan pemeriksaan terhadap nilai kecil, melangkau nombor genap dan menggunakan i*i untuk mengekalkan ketepatan. ✅