Olimpiade Sains Kota (OSK) 2013 - Komputer, Nomor 34

kita analisis terlebih dahulu, apa yang sebenarnya fungsi wow(n) hitung?
Jika kita baca dan pelajari kodenya baikbaik,
rupanya jika faktorisasi prima dari n adalah p1^a1
* p2^a2 * … * pk^ak, maka wow(n) bernilai (a1+1) * (a2+1) * … * (ak+1).
Oleh karena itu, kita dapat saja mencoba memfaktorisasikan setiap pilihan jawaban:
32 = 2^5  >  wow(32) = 6
512 = 2^9 > wow(512) = 10
1000 = 2^3 * 5^3 >  wow(1000) = 4 * 4 = 16
48 = 2^4 * 3 >  wow(48) = 5 * 2 = 10
38 = 2 * 19 >  wow(38) = 2 * 2 = 4
Dari semua pilihan di atas, nilai n terkecil yang menghasilkan wow(n) = 10 adalah 48.

function wow(n) adalah sebuah program untuk mencari banyak faktor dengan cara memfaktoriasi primakan suatu bilangan n.

analisanya begini:

kita lihat step by step

for i:=2 to n do

penggalan program diatas artinya untuk menjalankan program dari 2 hingga n

if(n mod i = 0) then begin

nah untuk suatu nilai i, jika n mod i = 0, then lakukan sesuatu. artinya, penggalan program diatas ingin mengecek untuk i = 2 hingga i = n, jika n habis dibagi i, dengan kata lain jika i merupakan suatu faktor prima dari n. mungkin ada yang bertanya, kenapa faktor prima? bukan faktor biasa? nanti ada penjelasannya

cnt:= 0;

menghitung banyak pangkat dari suatu faktor prima. kita dapat mengetahui variable count sebenarnya merupakan penghitungan banyak faktor prima nanti seiring berjalannya program

 n:=n div i;

nah ini kan sama saat kita melakukan pohon faktor ketika sd dulu, untuk suatu bilangan n, ketika kita ingin melakukan pohon faktor, maka kita akan mengecek mulai dari bilangan prima terkecil dahulu, yaitu 2. jika n tidak habis dibagi 2 , lanjut ke prima selanjutnya. nah ini sama saja dengan program ini, dia mengecek mulai dari 2 apakah habis dibagi dengan n. nah sama juga ketika melakukan pohon faktor, yaitu jika bilangan n habis dibagi suatu faktor prima, misalkan 2, maka kita akan terus membagi bilangan tersebut hingga tidak bisa lagi dibagi 2. 

cnt:= cnt+1;

nah disinilah fungsi count, untuk menghitung banyak pembagian yang dilakukan, atau dengan kata lain menghitung pangkat suatu faktor prima pada faktoriasi prima. count akan kembali ter-reset menjadi 0 ketika ingin mengecek faktor selanjutnya

 

 res:=res*(cnt+1);

nah program ini adalah sebenarnya menghitung banyak faktor. mengapa demikian? misalkan untuk n = 10, faktorisasi primanya kan 2 x 5, atau 2¹ x 5¹. faktor-faktornya kan 1, 2, 5, 10 (sebanyak 4). nah kita bisa mendapat banyak faktor dengan melihat faktorisasi prima. n = 10, FP = 2 x 5, artinya banyak faktornya adalah pangkat suatu faktor prima + 1 ( + 1 karena termasuk faktor prima pangkat 0) dikalikan dengan cara yang sama pada faktor prima berikutnya.

 

nah setelah mengerti maksud dari program ini, berarti program ini ingin mencari angka terkecil dengan banyak faktor sebanyak 10. 10 kan hanya ada 2 kemungkinan perkalian, 1 x 10 atau 2 x 5. berarti bisa suatu_faktor_prima¹ * suatu_faktor_prima¹⁰ atau suatu_faktor_prima² * suatu_faktor_prima¹. kemungkinan pertama tidak mungkin, karena FP terkecil pun kalau dipangkatkan 10, pasti besar sekali. jadi kita pilih yang 2 dan 5. berarti kita pilih saja 2 FP terkecil, yaitu 2 dan 3. supaya n bisa menjadi terkecil, berarti pangkat yang besar kita gunakan untuk faktor prima yang lebih kecil, lalu pangkat yang kecil untuk faktor prima yang lebih besar. 

 

sehingga didapatkan jawaban 2^5-1 * 3^2-1 = 16 * 3 = 48(D)

 

saran saya untuk mengerjakan suatu pseudocode, sebaiknya dimengerti  maksud codenya, supaya tidak capek nguli. untuk soal ini, 10 masih kecil. kalau sudah > 1000, sudah sulit + buang waktu. kecuali memang ada beberapa soal yang harus nguli