Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas metode Saringan Erathosthenes dalam mencari bilangan prima yang tidak melebihi suatu bilangan bulat tertentu, contohnya tidak lebih dari 100. Saringan ini efektif karena hanya mencari faktor bilangan prima yang kurang dari 10, yaitu 2, 3, 5, dan 7. Dengan mengeliminasi kelipatan bilangan prima secara berurutan dari daftar bilangan 1-100, kita dapatkan daftar bilangan prima hingga 97. Meskipun efektif untuk bilangan kecil, saringan ini menjadi tidak efisien untuk bilangan yang terlalu besar.

Nah sekarang ada juga catatan yang sebetulnya sifat juga kalau kita punya bilangan bulat komposite yang tidak melebihi 100 dia pasti mempunyai faktor prima tidak melebihi 10.

Ini adalah sebetulnya akibat dari yang tadi yang n itu faktor primanya itu pasti lebih kecil sama dengan akar n.

Bilangan prima itu yang kurang dari 10 karena 100 itu kan 10 x 10 jadi abinya itu tadi diambil sama-sama 10

dan kita tahu bilangan prima yang kurang dari 10 itu cuma 2, 3, 5, 7.

Nah itu yang akan menjadi faktor bilangan prima dari bilangan yang tidak lebih dari 100.

Jadi kita bisa dengan algoritma tadi kemudian dengan teorema yang sebelumnya kita bisa mereduksi untuk mencari faktor dari bilangan prima dari suatu bilangan.

Nah kalau sekarang mungkin kalian bisa dengan cepat mencari faktorisasi ini dengan kemajuan teknologi.

Tapi zaman dahulu pada saat bilangan prima ini ditemukan atau dibahas itu merupakan suatu masalah yang cukup menarik

dan sampai sekarang pun itu tidak ada atau belum ada yang bisa membuat algoritma untuk mencari bilangan prima sampai yang tak hingga.

Salah satu cara yang dilakukan orang zaman dahulu kala kalau kamu sudah jauh sekali sebelumnya itu ada yang namanya saringan Erastosmalkais.

Cara ini itu digunakan untuk mencari bilangan prima yang tidak melebihi suatu bilangan bulat tertentu.

Caranya adalah kita tulis 1-100 kita daftar semua bilangan bulat antara 1-100 abis itu dilakukan saringan.

Jadi saringan pertama ini 1-100 itu kita cari yang kelipatan bilangan prima terkecil yaitu 2.

Jadi kita punya 2 sendiri 4, 6, 8, 10 dan seterusnya itu kita coretin semua dari listnya.

Nanti sisanya adalah suatu daftar lagi yang tadinya 4, 6, 8 itu sudah hilang.

Kemudian kita cari yang habis dibagi 3 atau faktornya adalah 3 kita coret semuanya.

Berikutnya lagi bukan 4 ya karena yang kelipatan 4 sudah tercoret tadi dengan yang pembagi 2.

Kita ambil yang bilangan prima selanjutnya yaitu 5.

Sisanya lagi kalau masih ada kita bagi lagi dengan bilangan prima selanjutnya yaitu 7.

Dan berikutnya lagi kan 8 itu sudah tercoret dengan pembagi 2, 9 sudah tercoret dengan pembagi 3, 10 juga sudah tercoret dengan pembagi 2.

Sehingga nanti kita dapatkan sisanya ada 1 sendiri kemudian 2, 3, 5, 7, 11, 13, 17, 19 dan seterusnya sampai 97.

Itu adalah bilangan prima yang lebih kecil atau sama dengan 100.

Jadi kalau jumlahnya tidak besar saringan error testness ini sangat efektif untuk mencari bilangan primanya.

Tapi kalau bilangannya terlalu besar ini agak tidak efisien.