Kode Program (Python)

# bilangan-prima-02,py
# oleh: hy
from math import sqrt

def apakah_prima(n: int) -> bool:
   """ Uji primalitas bilangan n dengan optimisasi 6k+1. """
   if n <= 3:
       return n > 1
   if n % 2 == 0 or n % 3 == 0:
       return False
   i = 5; batas = int(sqrt(n))
   while (i <= batas):
       if n % i == 0 or n % (i+2) == 0:
           return False
       i += 6
   return True

### Program Utama ###
[bawah, atas] = [int(batas) \
   for batas in \
       (input('\nInput batas bawah dan atas (dipisahkan koma): ')).split(',')]
prima = [n for n in range(bawah, atas+1) if apakah_prima(n)]
print(f'Bilangan prima di antara {bawah} dan {atas} adalah:\
   \n{", ".join([str(p) for p in prima])}')
____________

Pembahasan

Kalau tidak salah, saya pernah menjawab pertanyaan sejenis di sini, namun hanya dengan batas atas saja. Kali ini, sekalian saya lakukan optimisasi pada algoritma penentuan bilangan prima atau bukan.

Pada program terdahulu, proses menentukan apakah sebuah bilangan merupakan bilangan prima atau bukan dilakukan "secara naif", dengan iterasi dari 2 hingga 1 kurangnya dari bilangan tersebut; jika pada proses iterasi ditemukan faktor dari bilangan tersebut, maka bilangan tersebut bukan prima. Kasus terburuk terjadi ketika bilangan tersebut adalah bilangan prima. Iterasi akan dilakukan hingga n-2 kali.

Kali ini, algoritma tersebut dioptimisasi, dengan menambahkan analisis kasus awal apakah bilangan habis dibagi 2 atau habis dibagi 3. Iterasi dilakukan dari 5 hingga pembulatan dari akar kuadrat bilangan tersebut, dengan stepping +6. Dengan variabel iterator i, bilangan input merupakan bilangan prima jika pada semua tahap iterasinya bilangan tersebut tidak habis dibagi i dan i+2.

Jika metode ini membingungkan, silahkan cari literatur tentang optimisasi uji primalitas bilangan bulat.

Contoh hasil eksekusi

• Input batas bawah dan atas (dipisahkan koma): 20, 50
  Bilangan prima di antara 20 dan 50 adalah:
  23, 29, 31, 37, 41, 43, 47

• Input batas bawah dan atas (dipisahkan koma): 250, 400
  Bilangan prima di antara 250 dan 400 adalah:
  251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397

• Input batas bawah dan atas (dipisahkan koma): 1500, 2000
  Bilangan prima di antara 1500 dan 2000 adalah:
  1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999

• Input batas bawah dan atas (dipisahkan koma): 500000, 502000
  Bilangan prima di antara 500000 dan 502000 adalah:
  500009, 500029, 500041, 500057, 500069, 500083, 500107, 500111, 500113, 500119, 500153, 500167, 500173, 500177, 500179, 500197, 500209, 500231, 500233, 500237, 500239, 500249, 500257, 500287, 500299, 500317, 500321, 500333, 500341, 500363, 500369, 500389, 500393, 500413, 500417, 500431, 500443, 500459, 500471, 500473, 500483, 500501, 500509, 500519, 500527, 500567, 500579, 500587, 500603, 500629, 500671, 500677, 500693, 500699, 500713, 500719, 500723, 500729, 500741, 500777, 500791, 500807, 500809, 500831, 500839, 500861, 500873, 500881, 500887, 500891, 500909, 500911, 500921, 500923, 500933, 500947, 500953, 500957, 500977, 501001, 501013, 501019, 501029, 501031, 501037, 501043, 501077, 501089, 501103, 501121, 501131, 501133, 501139, 501157, 501173, 501187, 501191, 501197, 501203, 501209, 501217, 501223, 501229, 501233, 501257, 501271, 501287, 501299, 501317, 501341, 501343, 501367, 501383, 501401, 501409, 501419, 501427, 501451, 501463, 501493, 501503, 501511, 501563, 501577, 501593, 501601, 501617, 501623, 501637, 501659, 501691, 501701, 501703, 501707, 501719, 501731, 501769, 501779, 501803, 501817, 501821, 501827, 501829, 501841, 501863, 501889, 501911, 501931, 501947, 501953, 501967, 501971, 501997