Algoritma Faktorisasi Prima [Lazy Tutorial]

Faktor prima adalah daftar bilangan prima yang membentuk suatu bilangan. Misal 24 = 2 * 2 * 2 * 3 atau 24 = 2^3 * 3.

Langkah algoritma:

  1. Siapkan list bilangan prima, disini saya pakai s.d. angka 10.000 (2, 3, 5, 7…).
  2. Ketika ada input/sisa cek dulu apakah itu = bil.prima. Syarat in < 10000.
  3. Cari dulu akar input untuk [limit] counter prima. Sehingga secara teori, algoritma ini dapat meng-handle input hingga angka 100juta.
  4. Loop: bagi input dengan (bilangan prima 2 <= x <= limit). Jika habis dibagi maka itu adalah faktor prima. Hasil bagi simpan ke [sisa].
  5. Ulangi langkah 2-4 sampai sisa tidak bisa dibagi /= prima atau =1.

Tidak terlalu sulit kan? Tidak sampai 100 baris kode kok. Berikut hasilnya:

Output bisa kita kreasikan menjadi pohon faktor atau langsung cetak.

Terima kasih.

13 Januari 2020

Leave a Reply

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *