1. Selesaikan bilangan prima
1.1 Deskripsi
Pertama -tama, mari kita pahami konsepnya, apa itu bilangan prima? Bilangan prima: Jika angka hanya dapat dibagi dengan 1 dan itu sendiri, angka seperti itu disebut bilangan prima, dan angka yang sesuai disebut nomor jumlah. Berdasarkan konsep ini, kita dapat dengan cepat memikirkan suatu metode, yaitu mulai dari 1 dan terus -menerus menguji untuk melihat apakah ada angka yang dapat dibagi oleh mereka dari 1 ke dirinya sendiri.
Dari sudut pandang ini, sebenarnya sangat sederhana untuk menemukan bilangan prima. Apakah ada cara yang lebih nyaman bagi kami? Berikut adalah metode terkenal untuk menemukan bilangan prima oleh Eratosthenes.
1.2 Solusi
Pertama -tama, Anda dapat menggunakan lingkaran untuk menyelesaikan masalah ini. Bagilah angka yang ditentukan dengan semua angka yang lebih kecil dari itu. Jika Anda bisa memecah belahnya, itu bukan bilangan prima. Namun, bagaimana mengurangi jumlah pemeriksaan lingkaran? Bagaimana cara menemukan semua bilangan prima lebih kecil dari n?
Dengan asumsi bahwa nomor yang akan diperiksa adalah n, pada kenyataannya, periksa saja nomor root N. Alasannya sangat sederhana. Asumsikan bahwa a*b = n, jika a lebih besar dari nomor root N, pada kenyataannya, periksa sebelum kurang dari A dapat pertama -tama memeriksa bahwa angka B dapat dibagi. Namun, menggunakan nomor root dalam program akan memiliki masalah akurasi, sehingga Anda dapat menggunakan i*i <= n untuk memeriksa dan eksekusi akan lebih cepat.
Mari kita asumsikan bahwa ada saringan untuk menyimpan 1 ~ n, misalnya:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ......... n
Sift Pertama kelipatan 2:
2 3 5 7 9 11 13 15 17 19 21 ......... n
Lalu sapilah kelipatan 3:
2 3 5 7 11 13 17 19 ......... n
Kemudian sari kelipatan 5, lalu sari bilangan prima 7, lalu sari kelipatan 11 ..., dengan cara ini, angka -angka yang ditinggalkan pada akhirnya adalah semua bilangan prima, ini adalah metode penyaringan Eratosthenes (eratosthenessieveMethod).
Jumlah cek dapat dikurangi. Faktanya, cukup periksa 6n+1 dan 6n+5, yaitu, lewati kelipatan 2 dan 3 secara langsung, sehingga tindakan pemeriksaan IF dalam program dapat dikurangi.
1.3 Kode
impor java.util.*; kelas publik prime {public static int [] findPrimes (final int max) {int [] prime = new int [max+1]; Daftar ArrayList = ArrayList baru (); untuk (int i = 2; i <= max; i ++) prime [i] = 1; untuk (int i = 2; i*i <= max; i ++) {// Ini dapat ditingkatkan if (prime [i] == 1) {for (int j = 2*i; j <= max; j ++) {if (j % i == 0) prime [j] = 0; }}} untuk (int i = 2; i <max; i ++) {if (prime [i] == 1) {list.add (integer baru (i)); }} int [] p = int new int [list.size ()]; Objek [] objs = list.toArray (); untuk (int i = 0; i <p.length; i ++) {p [i] = ((integer) objs [i]). intvalue (); } return p; } public static void main (string [] args) {int [] prime = prime.findprimes (1000); untuk (int i = 0; i <prime.length; i ++) {System.out.print (prime [i]+""); } System.out.println (); }}2. Faktorisasi
2.1 Deskripsi
Seperti yang ditunjukkan di atas, mari kita pahami faktorisasi apa itu? Mengubah angka menjadi produk dari beberapa angka lain disebut faktorisasi. Setelah memahami konsep ini, kita harus dapat memahami bahwa kita sedang memecahkan faktor jumlah jumlah dibandingkan dengan solusi di atas untuk menyelesaikan bilangan prima.
Faktorisasi pada dasarnya menggunakan nilai lebih kecil dari angka input sebagai pembagi, dan menghapusnya dengan nomor input. Jika dapat dibagi, itu akan dianggap sebagai faktor. Solusi yang lebih cepat adalah menemukan semua bilangan prima lebih kecil dari angka dan mencoba untuk melihat apakah itu dapat dibagi.
2.2 Kode
impor java.util.arraylist; faktor kelas publik {public static int [] faktor (int num) {int [] pnum = prime.findprimes (num); Daftar ArrayList = ArrayList baru (); untuk (int i = 0; pnum [i] * pnum [i] <= num;) {if (num % pnum [i] == 0) {list.add (integer baru (pnum [i])); num /= pnum [i]; } lain i ++; } list.add (integer baru (num)); int [] f = int new [list.size ()]; Objek [] objs = list.toArray (); untuk (int i = 0; i <f.length; i ++) {f [i] = ((integer) objs [i]). intvalue (); } return f; } public static void main (string [] args) {int [] f = factor.factor (100); untuk (int i = 0; i <f.length; i ++) {System.out.print (f [i]+""); } System.out.println (); }}3. Ringkasan
Memecahkan bilangan dan faktorisasi utama adalah keterampilan dasar program pembelajaran dan algoritma, dan Anda harus menguasainya dengan mahir. Kode di sini hanya memiliki sejumlah kecil komentar, yang mungkin sedikit sulit bagi pemula, tetapi ini adalah langkah pertama untuk memasuki algoritma Istana Program. Anda dapat menyalin kode ini ke mesin Anda dan mengisi komentar langkah demi langkah untuk membuat proses program Anda lebih jelas.
Di atas adalah semua konten dari artikel ini tentang implementasi pemrograman Java untuk mencapai bilangan prima dan kode faktorisasi, dan saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya!