Project Euler Problem 5

Saya suka tipe soal yang ini, tidak perlu coding, hanya menggunakan kertas dan pensil, coret-coret sedikit, dapat hasilnya.

Problem Description:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Note: evenly divisible = habis dibagi.


Solusi dari problem ini adalah menggunakan Kelipatan Persekutuan Terkecil (KPK) yang telah dipelajari sewaktu zaman Sekolah Dasar. Metode yang saya gunakan adalah faktorisasi prima. Saya ingat betul diajarin beginian sewaktu kelas 4 SD. (well, ternyata jadi murid SD di Indonesia itu susah ya :P)

Pertama kita mencari bentuk faktorisasi prima dari bilangan 2-20 (1 tidak dihitung karena semua bilangan pasti habis dibagi 1) dengan menggunakan pohon faktor. Didapatlah:

2 = 2
3 = 3
4 = 2^2
5 = 5
6 = 2 \times 3
7 = 7
8 = 2^3
9 = 3^2
10 = 2 \times 5
11 = 11
12 = 2^2 \times 3
13 = 13
14 = 2 \times 7
15 = 3 \times 5
16 = 2^4
17 = 17
18 = 2 \times 3^2
19 = 19
20 = 2^2 \times 5

Untuk mencari KPKnya, kita cukup mengalikan semua faktor prima dari bilangan-bilangan di atas, jika ada yang sama, dipilih yang pangkatnya paling besar. Sehingga diperoleh:
\text{lcm} = 2^4 \times 3^2 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19

I got the result!

2 thoughts on “Project Euler Problem 5

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s