Olimpiade Sains Kota (OSK) 2019 - Komputer, Nomor 8

Question

Bilangan ajaib adalah bilangan yang memiliki jumlah faktor yang menyisakan 1 apabila dibagi 4, sebagai contoh adalah angka 1, 1 memiliki 1 buah faktor (yaitu 1). Untuk kesekian kalinya, pak Dengklek ingin meminta tolong kalian untuk menghitung ada berapa banyak bilangan ajaib yang berada diantara 1 dan 300 inklusif. Ada berapakah bilangan ajaib yang ingin diketahui pak Dengklek?
a. 9
b. 5
c. 2
d. 4
e. 8

Muhammad Ramzi · Accepted Answer

Misalkan banyak faktor dari bilangan n ditulis BF(n)
Ingat, sembarang bilangan asli n kecuali 1 dapat ditulis dalam bentuk faktorisasi prima:
$n=p_1^{n_1}\times p_2^{n_2}\times p_3^{n_3}\times\cdots$
$p_1,p_2,\cdots,p_n$ merupakan bilangan prima.
Nah, menghitung banyak faktor dari n bisa didapat dengan rumus:
$BF(n)=(n_1+1)\times(n_2+1)\times(n_3+1)\times\cdots$
Nah karena banyak faktornya bersisa 1 jika dibagi 4, bisa dikatakan:
$BF(n)\equiv1[4]$
[4] itu (mod 4) yah...
nah dari aritmatika modular, didapat:
$BF(n)\equiv1[4]\equiv5[4]\equiv9[4]\equiv13[4]\equiv\cdots$

Olimpiade Sains Kota (OSK) 2019 - Komputer, Nomor 8

1 jawaban