Jika bilangan asli lebih besar dari 1 dan tidak memiliki pembagi positif selain 1 dan bilangan itu sendiri, dst
Sebagai contoh. 3, 7, 11 dst adalah bilangan prima
Angka komposit
Bilangan asli lain yang bukan bilangan prima disebut bilangan komposit
Misalnya. 4, 6, 9 dst. adalah bilangan komposit
Mari kita lihat contoh berikut untuk memahami implementasinya
Contoh
Keluaran
Enter an input number:17 17 is a prime number
Penjelasan
Kami telah menggunakan kondisi if else bersarang untuk memeriksa apakah bilangan tersebut bilangan prima atau bukan
Pertama, kami telah memeriksa apakah angka yang diberikan lebih besar dari 1 atau tidak. Jika tidak lebih besar dari 1, maka angka tersebut akan langsung menuju ke bagian lain dan mencetak 'bukan bilangan prima. '
Sekarang, angka tersebut akan masuk ke dalam for loop dimana kita melakukan Iterasi dari 2 ke angka/2. Kemudian, kami menggunakan kondisi if else bersarang di dalam for loop. Jika bilangan tersebut benar-benar habis dibagi oleh 'i', maka itu bukanlah bilangan prima;
Jika Anda pernah mengikuti tes pengkodean, Anda akan menemukan pertanyaan matematika pada tes keutamaan atau untuk memeriksa apakah suatu bilangan prima. Dan selama beberapa menit berikutnya, Anda akan belajar menemukan solusi optimal untuk pertanyaan ini
Dalam tutorial ini, Anda akan
- mengulas dasar-dasar bilangan prima,
- tulis kode Python untuk memeriksa apakah suatu bilangan prima, dan
- optimalkan lebih lanjut untuk mendapatkan algoritma runtime O(√n).
Untuk semua ini dan lebih banyak lagi, mari kita mulai
Apa itu Bilangan Prima?
Mari kita mulai dengan meninjau dasar-dasar bilangan prima
Dalam teori bilangan, bilangan asli n dikatakan prima jika memiliki tepat dua faktor. 1 dan bilangan itu sendiri (n). Ingat dari matematika sekolah Anda. suatu bilangan i dikatakan sebagai faktor dari bilangan n, jika i membagi n secara merata. ✅
Tabel berikut mencantumkan beberapa angka, semua faktornya, dan jika bilangan prima
nFaktor adalah Prima?11Tidak21, 2Ya31, 3Ya41, 2, 4No71, 7Ya151, 3, 5, 15TidakDari tabel di atas, kita dapat menuliskan yang berikut ini
- 2 adalah bilangan prima terkecil
- 1 adalah faktor dari setiap bilangan
- Setiap angka n adalah faktor dari dirinya sendiri
Jadi 1 dan n adalah faktor sepele untuk sembarang bilangan n. Dan bilangan prima seharusnya tidak memiliki faktor selain keduanya
Ini berarti bahwa ketika Anda beralih dari 2 ke n – 1, Anda seharusnya tidak dapat menemukan faktor nontrivial yang membagi n tanpa sisa
O(n) Algoritma untuk Memeriksa apakah suatu Angka adalah Prima dengan Python
Pada bagian ini, mari kita meresmikan pendekatan di atas ke dalam fungsi Python
Anda dapat mengulang semua angka dari 2 hingga n – 1 menggunakan objek range() dengan Python
Dengan Python, is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True_0 mengembalikan objek jangkauan. Anda kemudian dapat mengulangi objek rentang untuk mendapatkan urutan dari is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True1 hingga is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True2 dalam langkah is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True3
Karena kita membutuhkan himpunan bilangan bulat dari 2 sampai n-1, kita dapat menentukan is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True4 dan menggunakannya bersamaan dengan is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True5 loop
Inilah yang ingin kami lakukan
- Jika kamu menemukan sebuah bilangan yang habis membagi n tanpa sisa, kamu bisa langsung menyimpulkan bahwa bilangan tersebut bukan bilangan prima
- Jika Anda telah mengulang seluruh rentang angka dari 2 hingga n – 1 tanpa menemukan angka yang membagi n secara merata, maka angka tersebut adalah bilangan prima
Fungsi Python untuk Memeriksa Bilangan Prima
Dengan menggunakan di atas, kita dapat melanjutkan dan mendefinisikan fungsi is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True6 sebagai berikut
def is_prime(n): for i in range(2,n): if (n%i) == 0: return False return True_Sekarang mari kita parsing definisi fungsi di atas
- Fungsi di atas is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True_6 menggunakan bilangan bulat positif n sebagai argumennya
- Jika Anda menemukan faktor dalam rentang yang ditentukan dari (2, n-1), fungsi mengembalikan is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True8—karena angka tersebut bukan bilangan prima
- Dan itu mengembalikan is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True_9 jika Anda melintasi seluruh loop tanpa menemukan faktor
Selanjutnya, mari kita panggil fungsi dengan argumen dan verifikasi apakah hasilnya benar
is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True_Pada output di atas, Anda melihat bahwa 2 dan 11 adalah bilangan prima (fungsi mengembalikan is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True9). Dan 8 dan 9 bukan bilangan prima (fungsi mengembalikan is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True8)
Cara Mengoptimalkan Fungsi Python is_prime()
Kami dapat melakukan pengoptimalan kecil di sini. Perhatikan daftar faktor pada tabel di bawah ini
NumberFactors61, 2, 3, 6101, 2, 5, 10181, 2, 3, 6, 9, 18Kita dapat melihat bahwa satu-satunya faktor n yang lebih besar dari n/2 adalah n itu sendiri
Jadi ini berarti Anda tidak perlu mengulang sampai n - 1. Anda malah dapat menjalankan loop hanya hingga n/2
Jika Anda tidak menemukan faktor non-trivial hingga n/2, Anda juga tidak dapat menemukannya di luar n/2
Sekarang mari kita ubah fungsi is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True_6 untuk memeriksa faktor dalam rentang (2, n/2)
def is_prime(n): for i in range(2,int(n/2)): if (n%i) == 0: return False return TrueMari lanjutkan dan verifikasi output melalui beberapa pemanggilan fungsi
is_prime(9) # False is_prime(11) # TrueMeskipun sepertinya kami telah mengoptimalkan, algoritme ini tidak lebih efisien daripada yang sebelumnya dalam hal kompleksitas runtime. Faktanya, keduanya memiliki kompleksitas runtime O(n). sebanding dengan nilai n atau linier dalam n
Bisakah kita berbuat lebih baik?
▶️ Lanjutkan ke bagian selanjutnya untuk menentukan cara meningkatkan kompleksitas waktu untuk pengujian bilangan prima
O(√n) Algoritma untuk Memeriksa Bilangan Prima dengan Python
Kebetulan faktor-faktor suatu bilangan berpasangan
Jika a adalah faktor dari bilangan n, maka ada juga faktor b sehingga a x b = n, atau sederhananya, ab = n
Mari kita verifikasi ini melalui sebuah contoh
Tabel di bawah ini menunjukkan faktor-faktor dari angka 18 yang terjadi secara berpasangan. Anda dapat memverifikasi hal yang sama untuk beberapa nomor lagi jika Anda mau
Perhatikan juga bahwa √18 kira-kira sama dengan 4. 24
Dan pada faktor-faktor yang berpasangan (a,b), Anda dapat melihat bahwa jika a kurang dari 4. 24, maka b lebih besar dari 4. 24—dalam contoh ini, (2, 18) dan (3, 6)
Faktor dari 18 berpasanganGambar di bawah menunjukkan faktor dari 18 yang diplot pada garis bilangan
Jika angka n merupakan kuadrat sempurna, Anda akan memiliki a = b = √n sebagai salah satu faktornya
▶️ Perhatikan faktor dari 36 pada tabel di bawah ini. Karena 36 adalah kuadrat sempurna, a = b = 6 adalah salah satu faktornya. Untuk semua pasangan faktor lainnya (a, b), berlaku a < 6 dan b > 6
Kesimpulannya, kami memiliki yang berikut ini
- Setiap angka n dapat ditulis sebagai n = a x b
- Jika n adalah kuadrat sempurna, maka a = b = √n
- Dan jika a < b, maka a < √n dan b > √n
- Selain itu, jika a > b, maka a > √n dan b < √n
Jadi alih-alih mengulang semua bilangan bulat hingga n/2, Anda dapat memilih untuk menjalankan hingga √n. Dan ini jauh lebih efisien daripada pendekatan kami sebelumnya
Cara Memodifikasi Algoritma is_prime() menjadi O(√n).
Mari lanjutkan untuk mengoptimalkan fungsi untuk memeriksa bilangan prima dengan Python
import math def is_prime(n): for i in range(2,int(math.sqrt(n))+1): if (n%i) == 0: return False return TrueSekarang, mari kita parsing definisi fungsi di atas
- Untuk menghitung akar kuadrat dari sebuah angka, mari impor modul matematika bawaan Python, dan gunakan fungsi def is_prime(n): for i in range(2,int(n/2)): if (n%i) == 0: return False return True3
- Karena n mungkin bukan kuadrat sempurna, kita harus memasukkannya ke dalam bilangan bulat. Gunakan def is_prime(n): for i in range(2,int(n/2)): if (n%i) == 0: return False return True_4 untuk mentransmisikan def is_prime(n): for i in range(2,int(n/2)): if (n%i) == 0: return False return True5 menjadi def is_prime(n): for i in range(2,int(n/2)): if (n%i) == 0: return False return True6
- Untuk memastikan kami benar-benar memeriksa hingga √n, kami menambahkan plus satu karena fungsi range() mengecualikan titik akhir rentang secara default
Sel kode di bawah memverifikasi bahwa fungsi kami is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True6 berfungsi dengan benar
is_prime(8) # False is_prime(15) # False is_prime(23) # TrueDi bagian selanjutnya, mari kita buat beberapa plot sederhana untuk memahami O(n) dan O(√n) secara visual
Membandingkan O(n) dan O(√n) Secara Visual
▶️ Jalankan cuplikan kode berikut di lingkungan notebook Jupyter pilihan Anda
import numpy as np import seaborn as sns import pandas as pd n = 20 x = np.arange(n) y1 = np.sqrt(x) y2 = x df = pd.DataFrame({"O(√n)":y1,"O(n)":y2}) sns.set_theme() sns.lineplot(data = df)Cuplikan di atas menunjukkan bagaimana Anda dapat memplot kurva untuk n dan √n untuk rentang nilai
- Kami menggunakan fungsi NumPy arange() untuk membuat array angka
- Dan kemudian, kami mengumpulkan nilai n dan √n hingga, tetapi tidak termasuk 20, ke dalam DataFrame panda
- Selanjutnya, kami memplot menggunakan fungsi lineplot() seaborn
Dari plot di bawah ini, kita melihat bahwa √n secara signifikan lebih kecil dari n
Sekarang mari kita tingkatkan jangkauan hingga setinggi 2000 dan ulangi langkah yang sama seperti di atas
import numpy as np import seaborn as sns import pandas as pd n = 2000 x = np.arange(n) y1 = np.sqrt(x) y2 = x df = pd.DataFrame({"O(√n)":y1,"O(n)":y2}) sns.set_theme() sns.lineplot(data = df) _Dari plot di atas, Anda dapat menyimpulkan bahwa algoritme O(√n) secara signifikan lebih cepat saat Anda menguji jika bilangan besar adalah bilangan prima.
Ini contoh singkatnya. 2377 adalah bilangan prima—buktikan ini. 😀
Sementara pendekatan O(n) akan mengambil urutan 2000 langkah, algoritma O(√n) dapat membantu sampai pada jawaban hanya dalam 49 langkah. ✅
Kesimpulan
⏳ Dan saatnya untuk ringkasan singkat
- Untuk memeriksa apakah suatu bilangan prima, pendekatan naifnya adalah mengulang semua bilangan dalam rentang (2, n-1). Jika Anda tidak menemukan faktor yang membagi n, maka n adalah bilangan prima
- Karena satu-satunya faktor n yang lebih besar dari n/2 adalah n itu sendiri, Anda dapat memilih untuk menjalankan hanya hingga n/2
- Kedua pendekatan di atas memiliki kompleksitas waktu O(n)
- Karena faktor-faktor dari suatu bilangan muncul berpasangan, Anda hanya dapat menjalankan hingga √n. Algoritma ini jauh lebih cepat daripada O(n). Dan keuntungannya cukup besar saat memeriksa apakah bilangan besar itu prima atau tidak
Saya harap Anda mengerti cara memeriksa apakah suatu bilangan prima dengan Python. Sebagai langkah selanjutnya, Anda dapat melihat tutorial kami tentang program Python tentang operasi string—tempat Anda akan belajar memeriksa apakah string adalah palindrom, anagram, dan lainnya