Olimpiade Sains Provinsi (OSP) 2012 - Komputer, Nomor 8

cara mencari 4, 2, 1 dengan cara bruteforce dapat diminimalisir dengan cara memfaktorkan angka 30 yaitu 2¹ x 3¹ x 5¹

angka-angka 2,3, dan 5 dapat dibuat kombinasi yang menghasilkan (a+1) + (b+1) + (c+1) = 30, dalam kasus ini karena seluruh angka berpangkat 1 maka tidak ada yang harus kita coba lagi. hanya ada 1 kemungkinan yaitu

(a+1) = 2, a = 1

(b+1) = 3, b = 2

(c+1) = 4, c = 4

untuk mendapatkan angka terkecil, maka angka terbesar harus dipangkatkan ke basis terkecil dalam hal ini

2⁴ x 3² x 5¹ = 720

Banyaknya pembagi dari suatu bilangan dapat dicari dengan melakukan faktorisasi prima. Sebuah bilangan yang dapat direpresentasikan sebagai 2^a + 3^b + 5^c (dan seterusnya) akan memiliki pembagi sebanyak (a+1) x (b+1) x (c+1) dst.

Contoh:

12 = 2² + 3¹, berarti 12 memiliki pembagi sebanyak (2+1) x (1+1) = 6 pembagi

Sekarang kita ingin mencari bilangan terkecil yang memiliki tepat 30 pembagi. Berarti bilangan yang kita cari adalah 2^a + 3^b + 5^c terkecil dimana (a+1) x (b+1) x (c+1) = 30.

Jawabannya adalah a=4, b=2, c=1. Maka bilangan tersebut adalah 720.