Cara membuat pemeriksa bilangan prima dengan python

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

Dari 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)
# True

1 hingga

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

2 dalam langkah

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

3

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)
# True

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

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)
# True

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)
  # True

  8—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)
# True

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

Cara Mengoptimalkan Fungsi Python is_prime()

Kami dapat melakukan pengoptimalan kecil di sini. Perhatikan daftar faktor pada tabel di bawah ini

Kita 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

def is_prime(n):
  for i in range(2,int(n/2)):
    if (n%i) == 0:
      return False
  return True

Mari lanjutkan dan verifikasi output melalui beberapa pemanggilan fungsi

is_prime(9)
# False

is_prime(11)
# True

Meskipun 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)

Gambar 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 True

Sekarang, 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 True

  3
• 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 True

  5 menjadi

  def is_prime(n):
    for i in range(2,int(n/2)):
      if (n%i) == 0:
        return False
    return True

  6
• 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)
# True

is_prime(8)
# False

is_prime(15)
# False

is_prime(23)
# True

Di 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

Bagaimana Anda membuat pencari bilangan prima dengan Python?

Bagaimana Anda membuat kode pemeriksa bilangan prima?

Apa yang dilakukan Is_prime dengan Python?

Bagaimana cara memeriksa apakah suatu bilangan prima dalam Python menggunakan while loop?