Kata pengantar
Hari ini saya melihat pertanyaan yang membuatnya tampaknya tidak sulit untuk menentukan apakah angka adalah bilangan prima. Karena itu, saya memutuskan untuk mengimplementasikannya.
Struktur dom
<! Doctype html> <html lang = "en"> <Head> <meta charset = "utf-8"> <iteme> Hitung nomor prima dalam 500 dan output </iteme> <meta name = "viewport" content = "width = device-width, initial-scale = 1.0, skala maksimum = 1.0, skala pengguna = 0" src = "http://apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"> </script> </head> <body> <Div> <input type = "text" id = "num" value = ""> <input type = "Tombol" id = "kirim" value = "Kirim"> </div> </body> </html> <script> $ (function () {$ ("#kirim"). on ('click', function () {var num = $ ("#num"). val (); if (isPrimenum (num)) {warn (num+"adalah prime");} lainnya (iSprimenum (num)) {num+"adalah prime");} lainnya {num) {num+"adalah prime"); komposit ");}});}); </skrip>Seperti yang ditunjukkan di atas, kami menggunakan fungsi Isprimenum (NUM) untuk menentukan apakah itu bilangan prima. Mari kita terapkan fungsi ini di bawah ini.
Gunakan loop untuk menentukan apakah itu bilangan prima
fungsi isPrimenum (num) {for (var i = 2; i <num; i ++) {if (num%i == 0) {return false;}}; return true;}Prinsipnya relatif sederhana. Dengan terus menemukan sisanya dengan nomor target dengan 2 atau lebih, jika Anda bisa mendapatkan 0, itu berarti bahwa ini adalah bilangan gabungan daripada bilangan prima.
Tapi perhitungan ini tampaknya agak besar
Mengoptimalkan metode pertama
Ini sangat sederhana, diimplementasikan dalam waktu singkat. Namun, tampaknya kita dapat mengoptimalkannya. Kami tidak perlu mengejar nomor ini dan menemukan sisanya. Kita hanya perlu mengulang ke setengah dari nomor ini untuk menghitung apakah nomor ini adalah bilangan prima.
fungsi isPrimenum (num) {for (var i = 2; i <num/2+1; i ++) {if (num%i == 0) {return false;}; return true;}Setelah pengukuran yang sebenarnya, kecepatan memang telah sangat ditingkatkan, tetapi saya tahu bahwa mantissa dari jumlahnya bahkan atau 5, jadi jelas bukan bilangan prima, jadi tidak perlu menghitungnya. Mari kita optimalkan lagi
Tidak ada angka menghitung yang mantissanya bahkan atau 5
fungsi isPrimenum (num) {if (! isDual (num)) {return false;} untuk (var i = 2; i <num/2+1; i ++) {if (num%i == 0) {return false;}; return true;} function isDual (num) {var num = num.toString (); num.substring (num.length-1, num.length); return lastnum%2 == 0 || lastnum%5 == 0? Salah: true;}Melalui optimasi seperti itu, kita dapat mengurangi jumlah perhitungan dan setidaknya setengah dari jumlahnya. (Tetapi pengukuran aktual meningkatkan kinerja, karena angka -angka seperti itu dapat dengan cepat dinilai bahwa mereka bukan bilangan prima)
Di sini, fungsi substring () menemukan bahwa itu tidak dapat digunakan pada angka, tetapi hanya dapat digunakan pada string. Sayangnya, jadi nomornya diubah menjadi string terlebih dahulu.
Jika bukan pemrosesan angka atau integer
Apa yang harus saya lakukan jika input pengguna bukan angka atau desimal? Saya dengan cepat menulis dua metode untuk memprosesnya ...
fungsi isPrimenum (num) {if (! isnum (num)) {return false;} if (! isInteger (num)) {return false;} if (! isDual (num)) {return false;} for (var i = 2; i <num/2+1; i ++) {if (num%i == 0) isInteger (num) {return num == ~~ num? true: false;} function isnum (num) {var num = num.toString (); var lastnum = num.substring (num.length-1, num.length); return lastnum%2 == 0 || lastnum%5 == 0? Salah: true;}Dua tips digunakan di sini, satu adalah untuk membulatkan desimal ~~ num, dan yang lainnya adalah untuk mengubah string menjadi angka. +num.
Harap baca posting blog saya sebelumnya "JS Pretending Skills for Javascript Learning (I) oleh Fungleo"
Ini tidak meningkatkan efisiensi apa pun, tetapi hanya menghilangkan input kesalahan perhitungan. Mari kita pikirkan lagi, apakah ada cara untuk dengan cepat menentukan apakah itu bukan bilangan prima?
Hapus angka yang dapat dibagi dengan 3 dan jangan menghitung
fungsi isPrimenum (num) {if (! isnum (num)) {return false;} if (! isInteger (num)) {return false;} if (num == 2 || num == 3 || num == 5) {return true;} if (! isDual (num)) {return false;} if (! isthree; if rembar (! num/5+1; true: false;} function isnum (num) {return num == +num? true: false;} function isDual (num) {var num = num.toString (); var lastnum = num.substring (num.length-1, num.length); return lastnum%2 == 0 || lastnum%5 == 0? false: true;} function ISThree (num) {var str = num.toString (); var sum = 0; untuk (var i = 0; i <str.length; i ++) {sum+=+str.substring (i, i+1);}; return sum%3 == 0? Salah: true;}Di sini, pertama -tama kami mengubah angka menjadi string, kemudian membagi setiap bit string, tambahkan dan jumlah, dan menggunakan hasilnya dan 3 untuk menemukan yang tersisa, dan kemudian kami dapat mengetahui apakah nomor ini dapat dipisahkan oleh 3.
Haha saya sangat pintar ... kinerja tes yang sebenarnya belum banyak membaik, tetapi memang telah sedikit membaik. Itu sedikit tertekan
Namun, jika kami mengecualikan angka 3-divisi, maka kami tidak perlu menghitung setengahnya. Kita tidak perlu menghitung setengahnya, kita hanya perlu menghitung sepertiga. Selain itu, kami juga telah mengecualikan 5, jadi kami hanya perlu menghitung seperlima ...
Setelah penyesuaian cepat, efisiensi telah sangat ditingkatkan !!! Saya kuat ...
Namun, dengan cara ini, kode akan menentukan bahwa itu adalah bilangan komposit dalam 2/3/5. Oleh karena itu, kalimat lain perlu ditambahkan.
if (num == 2 || num == 3 || num == 5) {return true;}Metode orang lain
Lalu saya tidak bisa memikirkan metode optimasi ... jadi saya mencari dan menemukan solusi berikut. Saya terkejut !!!
Fungsi isPrimenum2 (num) {return!/^.? $ |^(..+?)/1+$/. Test (array (num+1) .join ('1'))}Metode reguler digunakan, memang pendek, tetapi saya bisa memahaminya bahkan jika saya membacanya !!!
Saya benar -benar tidak mengerti apa prinsipnya, jadi saya mengikuti tes praktis dan menemukan bahwa efisiensi kode saya jauh lebih tinggi dari kode ini. Dari sini kita dapat melihat bahwa metode saya masih sangat bagus !!
Dibutuhkan 1600ms untuk kode saya untuk mencetak semua bilangan prima dalam 100000, dan kode ini membutuhkan 160000ms. Dengan kata lain, kode saya hanya membutuhkan satu persen dari waktu.
Namun, jika ada yang bisa memahami kode ini, tolong jelaskan kepada saya ...
Mengisi kembali
Setelah membaca beberapa informasi terkait, tampaknya metode yang saya gunakan NUM/5 di atas tidak terlalu baik (hasilnya tidak salah). Ada cara yang lebih baik, yaitu menggunakan math.sqrt (num) untuk menemukan akar kuadrat.
Hasil tes kode saya adalah sebagai berikut
Seperti yang ditunjukkan pada gambar di atas, hasil perhitungan kode saya benar -benar benar. Namun, butuh 1638 milidetik. Masih terjadi setelah banyak tes.
Hasil tes metode root kuadrat adalah sebagai berikut
Seperti yang ditunjukkan pada gambar di atas, metode ini lebih ilmiah dan lebih cepat. Dibutuhkan beberapa tes, dan dibutuhkan antara 1150 milidetik hingga 1.250 milidetik. Dibandingkan dengan kinerja kode saya, sekitar 25%.
Saya juga menilai apakah digitnya genap atau 5, dan apakah jumlahnya dapat dibagi dengan 3, yang telah lama. Saya pasti berharap untuk mengurangi jumlah operasi. Tetapi kode -kode ini sendiri juga memiliki jumlah operasi. Saya akan menghapus semua kode saya dan kemudian melihatnya.
Kinerja telah ditingkatkan lagi. Tampaknya semua perhitungan saya dioptimalkan secara negatif!
Akhirnya, kodenya adalah sebagai berikut:
fungsi isPrimenum (num) {if (! isNum (num)) {return false;} if (! isInteger (num)) {return false;} untuk (var i = 2; i <= math.sqrt (num); i ++) {if%i == 0) {return false;} num; return return; true: false;} function isnum (num) {return num == +num? Benar: false;}Ringkasan: Itu sepenuhnya karena aritmatika saya yang buruk yang membuat saya pintar di depan. Namun, mempraktikkan teknik kecil juga bagus -_- |||
Akhirnya, mari kita lihat berapa lama waktu yang dibutuhkan untuk menghitung semua bilangan prima dalam 1 juta
Di atas adalah ringkasan metode untuk menilai apakah angka adalah bilangan prima yang diperkenalkan oleh editor. Saya harap ini akan membantu semua orang.