Latihan 2.5 Latihan Pemrograman

1. Saringan Eratosthenes.

Salah satu metode untuk menghitung semua bilangan prima yang lebih kecil daripada bilangan bulat positif tetap \(N\) adalah mencantumkan semua bilangan \(n\) sedemikian sehingga \(1 \lt n \lt N\text{.}\) Mulailah dengan mencoret semua kelipatan \(2\text{.}\) Selanjutnya, coret semua kelipatan \(3\text{.}\) Kemudian coret semua kelipatan \(5\text{.}\) Perhatikan bahwa \(4\) sudah dicoret. Lanjutkan dengan cara ini, dengan memperhatikan bahwa kita tidak perlu meneruskannya hingga \(N\text{;}\) cukup berhenti pada \(\sqrt{N}\text{.}\) Dengan menggunakan metode ini, hitung semua bilangan prima yang lebih kecil daripada \(N = 250\text{.}\) Kita juga dapat menggunakan metode ini untuk mencari semua bilangan bulat yang relatif prima terhadap suatu bilangan bulat \(N\text{.}\) Cukup coret faktor-faktor prima dari \(N\) beserta semua kelipatannya. Dengan menggunakan metode ini, tentukan semua bilangan yang relatif prima terhadap \(N= 120\text{.}\) Dengan menggunakan Saringan Eratosthenes, tulislah program yang menghitung semua bilangan prima yang lebih kecil daripada suatu bilangan bulat \(N\text{.}\)

2.

Misalkan \({\mathbb N}^0 = {\mathbb N} \cup \{ 0 \}\text{.}\) Fungsi Ackermann adalah fungsi \(A :{\mathbb N}^0 \times {\mathbb N}^0 \rightarrow {\mathbb N}^0\) yang didefinisikan oleh persamaan-persamaan

\begin{align*} A(0, y) & = y + 1,\\ A(x + 1, 0) & = A(x, 1),\\ A(x + 1, y + 1) & = A(x, A(x + 1, y))\text{.} \end{align*}

Gunakan definisi ini untuk menghitung \(A(3, 1)\text{.}\) Tulislah program untuk mengevaluasi fungsi Ackermann. Ubah program tersebut agar menghitung banyaknya pernyataan yang dijalankan ketika fungsi Ackermann dievaluasi. Berapa banyak pernyataan yang dijalankan dalam evaluasi \(A(4, 1)\text{?}\) Bagaimana dengan \(A(5, 1)\text{?}\)

3.

Tulislah program komputer yang mengimplementasikan algoritma Euklides. Program tersebut harus menerima dua bilangan bulat positif \(a\) dan \(b\) sebagai masukan serta menghasilkan \(\gcd( a,b)\) beserta bilangan bulat \(r\) dan \(s\) sedemikian sehingga

\begin{equation*} \gcd( a,b) = ra + sb\text{.} \end{equation*}