Mencari faktor bilangan

Artikel ini menunjukkan algoritma untuk mencari faktor dari sebuah bilangan bulat.

Cara paling sederhana untuk mencari faktor

Cara paling sederhana adalah memeriksa seluruh bilangan yang lebih kecil dari bilangan yang dicari faktornya (misal: bil). Masing-masing bilangan diperiksa menggunakan operasi modulus, jika ia membagi bil tanpa sisa, maka ia adalah faktor dari bil. Implementasi dari cara ini diperlihatkan pada kode di bawah (silahkan dijalankan).

Penyempurnaan dengan efisiensi pada loop

Cara sebelumnya dapat disempurnakan, dimana cara tersebut masih melakukan perulangan dilakukan lebih dari yang diperlukan. Perulangan sebenarnya tidak perlu melibatkan seluruh bilangan yang lebih kecil dari bil, karena setiap faktor berpasangan dengan faktor lainnya. Kita cukup melakukan perulangan hingga √bil, karena faktor yang lebih besar dari √bil adalah pasangan pengali dari faktor yang lebih kecil dari √bil, yang sudah ditemukan pada iterasi sebelumnya.

Lihat kode berikut untuk implementasinya

Mencari faktor bilangan yang sangat besar (large numbers)

Dua cara sebelumnya hanya cocok untuk bilangan yang relatif kecil. Untuk bilangan yang sangat besar (misal, diatas 10¹⁶), keduanya akan memerlukan waktu yang terlalu lama. Solusi untuk kasus ini? Semoga dapat dibahas di kesempatan lainnya.

Semoga bermanfaat,

Salam