Tulislah program untuk menentukan semua bilangan prima yang kurang dari \(2000\) dengan pembagian percobaan. Tulislah program kedua yang menentukan semua bilangan kurang dari \(2000\) yang merupakan bilangan prima atau pseudoprima. Bandingkan kecepatan kedua program tersebut. Berapa banyak pseudoprima di bawah \(2000\text{?}\)

Terdapat bilangan komposit yang merupakan pseudoprima untuk setiap basis yang relatif prima terhadap bilangan tersebut. Bilangan-bilangan ini disebut bilangan Carmichael. Bilangan Carmichael pertama adalah \(561 = 3 \cdot 11 \cdot 17\text{.}\) Pada tahun 1992, Alford, Granville, dan Pomerance membuktikan bahwa terdapat tak berhingga banyak bilangan Carmichael [4]. Namun, bilangan Carmichael sangat jarang. Hanya ada \(2163\) bilangan Carmichael yang kurang dari \(25 \times 10^9\text{.}\) Untuk uji keprimaan yang lebih canggih, lihat [1], [6], atau [7].