Làm thế nào để bạn biết nếu một số là số nguyên tố trong python?

Nếu số tự nhiên lớn hơn 1 và không có ước dương nào khác ngoài 1 và chính số đó, v.v.

Ví dụ. 3, 7, 11 là các số nguyên tố

Hợp số

Các số tự nhiên khác không phải là số nguyên tố được gọi là hợp số

Ví dụ. 4, 6, 9, v.v. là hợp số

Chúng ta hãy xem ví dụ sau để hiểu việc thực hiện

Ví dụ

đầu ra

Enter an input number:17
17 is a prime number

Giải trình

Chúng ta đã sử dụng điều kiện if lồng nhau để kiểm tra xem một số có phải là số nguyên tố hay không

Đầu tiên, chúng tôi đã kiểm tra xem số đã cho có lớn hơn 1 hay không. Nếu nó không lớn hơn 1, thì số đó sẽ trực tiếp đến phần khác và in ra 'không phải là số nguyên tố. '

Bây giờ, số sẽ nhập vào vòng lặp for nơi chúng tôi thực hiện Lặp lại từ 2 đến số/2. Sau đó, chúng ta sử dụng điều kiện if lồng nhau bên trong vòng lặp for. Nếu số đó chia hết cho 'i' thì đó không phải là số nguyên tố;

Số nguyên tố là số tự nhiên lớn hơn 1 không là tích của hai số tự nhiên bé hơn. Số nào lớn hơn 1 và chỉ có hai ước là 1 và chính nó thì được gọi là số nguyên tố

Giả sử sau đây là đầu vào của chúng tôi -

7

Đầu ra phải như sau -

Prime Number

Kiểm tra xem một số có phải là số nguyên tố hay không

Hãy để chúng tôi kiểm tra xem một số có phải là số Nguyên tố hay không bằng cách sử dụng vòng lặp for –

Ví dụ

đầu ra

5 is a prime number

Kiểm tra xem một số có phải là Prime hay không bằng cách sử dụng sqrt()

Hãy để chúng tôi kiểm tra xem một số có phải là số Nguyên tố hay không bằng cách sử dụng phương thức sqrt() -

Ví dụ

đầu ra

9 is Not a Prime Number!

---

Nếu bạn đã từng làm các bài kiểm tra mã hóa, bạn sẽ bắt gặp câu hỏi toán học trong bài kiểm tra tính nguyên tố hoặc kiểm tra xem một số có phải là số nguyên tố hay không. Và trong vài phút tới, bạn sẽ học cách đưa ra giải pháp tối ưu cho câu hỏi này

Trong hướng dẫn này, bạn sẽ

• xem lại kiến ​​thức cơ bản về số nguyên tố,
• viết mã Python để kiểm tra xem một số có phải là số nguyên tố hay không và
• tối ưu hóa nó hơn nữa để có được thuật toán thời gian chạy O(√n)

Đối với tất cả những điều này và hơn thế nữa, hãy bắt đầu

Một số nguyên tố là gì?

Hãy bắt đầu bằng cách xem xét các khái niệm cơ bản về số nguyên tố

Theo lý thuyết số, một số tự nhiên n được gọi là số nguyên tố nếu nó có đúng hai ước. 1 và chính số đó (n). Nhớ lại từ toán trường học của bạn. một số i được gọi là một ước số của số n, nếu tôi chia n đều. ✅

Bảng sau đây liệt kê một vài số, tất cả các thừa số của chúng và nếu chúng là số nguyên tố

nThừa sốLà số nguyên tố?11Không21, 2Có31, 3Có41, 2, 4Không71, 7Có151, 3, 5, 15Không

Từ bảng trên, chúng ta có thể viết ra những điều sau đây

• 2 là số nguyên tố nhỏ nhất
• 1 là thừa số của mọi số
• Mỗi số n là một thừa số của chính nó

Vì vậy, 1 và n là các yếu tố tầm thường cho bất kỳ số n. Và một số nguyên tố không được có ước số nào khác ngoài hai ước số này

Điều này có nghĩa là khi bạn đi từ 2 đến n – 1, bạn sẽ không thể tìm thấy một thừa số không tầm thường chia n mà không có phần dư

Thuật toán O(n) để kiểm tra xem một số có phải là số nguyên tố trong Python không

Trong phần này, chúng ta hãy chính thức hóa cách tiếp cận trên thành một hàm Python

Bạn có thể lặp qua tất cả các số từ 2 đến n – 1 bằng cách sử dụng đối tượng range() trong Python

Trong Python,

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

0 trả về một đối tượng phạm vi. Sau đó, bạn có thể lặp lại đối tượng phạm vi để có được một chuỗi từ

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

1 cho đến

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

2 theo các bước của

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

3

Vì chúng tôi cần tập hợp các số nguyên từ 2 đến n-1, chúng tôi có thể chỉ định

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

4 và sử dụng nó cùng với vòng lặp

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

5

Đây là những gì chúng tôi muốn làm

• Nếu tìm một số chia n đều không dư thì có thể kết luận ngay số đó không phải là số nguyên tố

• Nếu bạn đã lặp qua toàn bộ dãy số từ 2 cho đến n – 1 mà không tìm thấy số nào chia hết cho n thì số đó là số nguyên tố

Hàm Python để kiểm tra số nguyên tố

Sử dụng cách trên, chúng ta có thể tiếp tục và định nghĩa hàm

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

6 như sau

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

Bây giờ chúng ta hãy phân tích định nghĩa hàm trên

• Hàm trên

  is_prime(2)
  # True
  
  is_prime(8)
  # False
  
  is_prime(9)
  # False
  
  is_prime(11)
  # True

  6 lấy một số nguyên dương n làm đối số
• Nếu bạn tìm thấy một thừa số trong phạm vi đã chỉ định là (2, n-1), hàm sẽ trả về

  is_prime(2)
  # True
  
  is_prime(8)
  # False
  
  is_prime(9)
  # False
  
  is_prime(11)
  # True

  8—vì số đó không phải là số nguyên tố
• Và nó trả về

  is_prime(2)
  # True
  
  is_prime(8)
  # False
  
  is_prime(9)
  # False
  
  is_prime(11)
  # True

  9 nếu bạn đi qua toàn bộ vòng lặp mà không tìm thấy thừa số

Tiếp theo, hãy gọi hàm với các đối số và xác minh xem đầu ra có đúng không

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

Trong kết quả ở trên, bạn thấy rằng 2 và 11 là số nguyên tố (hàm trả về

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

9). Và 8 và 9 không phải là số nguyên tố (hàm trả về

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

8)

Cách tối ưu hóa hàm is_prime() của Python

Chúng ta có thể thực hiện một tối ưu hóa nhỏ tại đây. Quan sát danh sách các yếu tố trong bảng dưới đây

Hệ Số61, 2, 3, 6101, 2, 5, 10181, 2, 3, 6, 9, 18

Chà, chúng ta có thể thấy rằng thừa số duy nhất của n lớn hơn n/2 là chính n

Vì vậy, điều này có nghĩa là bạn không cần phải lặp đến n – 1. Thay vào đó, bạn chỉ có thể chạy vòng lặp tối đa n/2

Nếu bạn không tìm thấy một yếu tố không tầm thường cho đến n/2, thì bạn cũng không thể tìm thấy một yếu tố vượt quá n/2

Bây giờ, hãy sửa đổi hàm

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

6 để kiểm tra các thừa số trong phạm vi (2, n/2)

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

Hãy tiếp tục và xác minh đầu ra thông qua một vài lời gọi hàm

is_prime(9)
# False

is_prime(11)
# True

Mặc dù có vẻ như chúng tôi đã tối ưu hóa, nhưng thuật toán này không hiệu quả hơn thuật toán trước về độ phức tạp của thời gian chạy. Trên thực tế, cả hai đều có độ phức tạp thời gian chạy O(n). tỷ lệ thuận với giá trị của n hoặc tuyến tính theo n

Chúng ta có thể làm tốt hơn không?

▶️ Chuyển sang phần tiếp theo để xác định cách cải thiện độ phức tạp về thời gian cho kiểm tra số nguyên tố

Thuật toán O(√n) để kiểm tra số nguyên tố trong Python

Nó xảy ra rằng các yếu tố của một số xảy ra theo cặp

Nếu a là một thừa số của số n, thì cũng tồn tại một thừa số b sao cho a x b = n, hay đơn giản là ab = n

Hãy xác minh điều này thông qua một ví dụ

Bảng dưới đây cho thấy các yếu tố của số 18 xảy ra theo cặp. Bạn có thể xác minh tương tự cho một vài số khác nếu bạn muốn

Ngoài ra, lưu ý rằng √18 xấp xỉ 4. 24

Và trong các thừa số xảy ra theo cặp (a, b), bạn có thể thấy rằng nếu a nhỏ hơn 4. 24 thì b lớn hơn 4. 24—trong ví dụ này, (2, 18) và (3, 6)

Thừa số của 18 theo cặp

Hình dưới đây cho thấy các thừa số của 18 được vẽ trên trục số

Nếu số n là số chính phương, bạn sẽ có a = b = √n là một trong các thừa số

▶️ Hãy xem các thừa số của 36 trong bảng bên dưới. Vì 36 là số chính phương nên a = b = 6 là một trong các thừa số. Đối với tất cả các cặp nhân tố khác (a, b), a < 6 và b > 6 đúng

Thừa số của 36 theo cặp

Tóm lại, chúng tôi có những điều sau đây

• Mỗi số n có thể được viết là n = a x b
• Nếu n là số chính phương thì a = b = √n
• Và nếu a < b thì a < √n và b > √n
• Mặt khác, nếu a > b thì a > √n và b < √n

Vì vậy, thay vì lặp qua tất cả các số nguyên lên tới n/2, bạn có thể chọn chạy tới √n. Và điều này hiệu quả hơn rất nhiều so với cách tiếp cận trước đây của chúng tôi

Cách sửa đổi thuật toán is_prime() thành O(√n)

Tiến hành tối ưu hàm kiểm tra số nguyên tố trong 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

Bây giờ, hãy phân tích cú pháp định nghĩa hàm trên

• Để tính căn bậc hai của một số, hãy nhập mô-đun toán học tích hợp sẵn của Python và sử dụng hàm

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

  3
• Vì n có thể không phải là số chính phương nên chúng ta sẽ phải chuyển nó thành một số nguyên. Sử dụng

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

  4 để biến

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

  5 thành một

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

  6
• Để đảm bảo rằng chúng tôi thực sự đang kiểm tra tới √n, chúng tôi thêm một dấu cộng vì hàm range() loại trừ điểm cuối của phạm vi theo mặc định

Ô mã bên dưới xác minh rằng chức năng của chúng tôi

is_prime(2)
# True

is_prime(8)
# False

is_prime(9)
# False

is_prime(11)
# True

6 hoạt động chính xác

is_prime(8)
# False

is_prime(15)
# False

is_prime(23)
# True

Trong phần tiếp theo, chúng ta hãy tạo một vài biểu đồ đơn giản để hiểu O(n) và O(√n) một cách trực quan

So sánh trực quan O(n) và O(√n)

▶️ Chạy đoạn mã sau trong môi trường máy tính xách tay Jupyter mà bạn chọn

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)

Đoạn mã trên cho thấy cách bạn có thể vẽ các đường cong cho n và √n cho một dải giá trị

• Chúng tôi sử dụng hàm NumPy arange() để tạo một mảng số
• Và sau đó, chúng tôi thu thập các giá trị của n và √n tối đa, nhưng không bao gồm 20, vào Khung dữ liệu gấu trúc
• Tiếp theo, chúng ta vẽ đồ thị bằng hàm lineplot() của seaborn

Từ biểu đồ bên dưới, chúng ta thấy rằng √n nhỏ hơn đáng kể so với n

Bây giờ chúng ta hãy tăng phạm vi lên cao nhất là 2000 và lặp lại các bước tương tự như trên

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)

Từ biểu đồ trên, bạn có thể suy ra rằng thuật toán O(√n) nhanh hơn đáng kể khi bạn kiểm tra xem một số lớn có phải là số nguyên tố hay không.

Đây là một ví dụ nhanh. 2377 là số nguyên tố—hãy xác minh điều này. 😀

Trong khi cách tiếp cận O(n) sẽ thực hiện theo thứ tự 2000 bước, thuật toán O(√n) có thể giúp đi đến câu trả lời chỉ sau 49 bước. ✅

Phần kết luận

⏳ Và đã đến lúc tóm tắt nhanh

• Để kiểm tra xem một số có phải là số nguyên tố hay không, cách tiếp cận ngây thơ là lặp qua tất cả các số trong phạm vi (2, n-1). Nếu bạn không tìm thấy một thừa số chia n, thì n là số nguyên tố
• Vì thừa số duy nhất của n lớn hơn n/2 là chính n, nên bạn có thể chọn chỉ chạy tối đa n/2
• Cả hai cách tiếp cận trên đều có độ phức tạp thời gian là O(n)
• Vì thừa số của một số xảy ra theo cặp nên bạn chỉ có thể chạy tối đa √n. Thuật toán này nhanh hơn rất nhiều so với O(n). Và mức tăng đáng kể khi kiểm tra xem một số lớn có phải là số nguyên tố hay không

Tôi hy vọng bạn hiểu cách kiểm tra xem một số có phải là số nguyên tố trong Python không. Bước tiếp theo, bạn có thể xem hướng dẫn của chúng tôi về các chương trình Python về thao tác chuỗi—nơi bạn sẽ học cách kiểm tra xem các chuỗi có phải là palindromes, đảo chữ cái, v.v.