Kiểm tra số nguyên tố trong python | Laptrinhcanban.com

HOME › >>

Kiểm tra số nguyên tố trong python

Hướng dẫn cách kiểm tra số nguyên tố trong python. Bạn sẽ học được cách viết hàm kiểm tra số nguyên tố trong python, cũng như cách liệt kê tất cả các số nguyên tố nhỏ hơn n bằng python sau bài học này.

Số nguyên tố trong python là gì

Chúng ta đều biết một số nguyên tố là một số tự nhiên lớn hơn 1 và chỉ có hai ước số dương phân biệt là 1 và chính nó. Điều này có nghĩa rằng một số nguyên tố không chia hết cho bất kỳ số nào khác ngoài 1 và chính nó.

Ví dụ, chúng ta xem xét các số 2, 3, 6 như sau:

Số 2 chỉ có đúng hai ước số là 1 và chính nó nên là số nguyên tố
Số 3 chỉ có đúng hai ước số là 1 và chính nó nên là số nguyên tố
Số 6 có 4 ước số là 1, 2 , 3 và 6, do đó nó không phải là số nguyên tố.

Cách kiểm tra số nguyên tố trong Python

Số nguyên tố là số lớn hơn 1chỉ có đúng hai ước số là 1 và chính nó. Bởi vậy nếu số đã cho có nhiều hơn dù chỉ 1 ước số khác số 1 và chính nó thì nó không phải là số nguyên tố.

Để làm được điều này, chúng ta chỉ cần kiểm tra trong phạm vi lớn hơn 1 và nhỏ hơn số đã cho có tồn tại ước số nào không, và nếu tồn tại dù chỉ một ước số thì có thể khẳng định số đã cho không phải là số nguyên tố.

Dựa vào điều này mà chúng ta có thể tạo hàm kiểm tra số nguyên tố trong python như sau:

def is_prime(n):
if n <= 1:
return False # Số không lớn hơn 1 không phải số nguyên tố

#Sử dụng vòng lặp for để kiểm tra có tồn tại ước số nào khác lớn hơn 1 không
for i in range(2, n):
if n % i == 0:
return False # Chỉ cần tìm thấy 1 ước số là biết không phải số nguyên tố

return True # Là số nguyên tố

Chúng ta có thể gọi hàm này và sử dụng để viết chương trình python kiểm tra số nguyên tố như dưới đây. Chương trình này có tác dụng nhập n kiểm tra n có phải số nguyên tố không không python.

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

n = int(input(">> nhap so tu nhien: "))

if is_prime(n):
print(f"{n} la so nguyen to")
else:
print(f"{n} khong phai so nguyen to")

Màn hình nhập liệu và kết quả chương trình python kiểm tra số nguyên tố sẽ như sau:

>> nhap so tu nhien: 1
1 khong phai so nguyen to

>> nhap so tu nhien: 2
2 la so nguyen to

>> nhap so tu nhien: 3
3 la so nguyen to

>> nhap so tu nhien: 4
4 khong phai so nguyen to

>> nhap so tu nhien: 6
6 khong phai so nguyen to

Tối ưu hóa kiểm tra số nguyên tố

Mặc dù cách trên hoạt động, nhưng nó có thể không hiệu quả với các số lớn. Vì vậy, chúng ta có thể tối ưu hóa cách kiểm tra số nguyên tố bằng cách giới hạn vòng lặp kiểm tra đến căn bậc hai của n. Điều này bởi vì nếu n có một ước số lớn hơn căn bậc hai của n, thì nó cũng phải có một ước số nhỏ hơn căn bậc hai của n. Vì vậy, chúng ta chỉ cần kiểm tra từ 2 đến căn bậc hai của n để đảm bảo tính nguyên tố.

Dưới đây là một ví dụ về cách kiểm tra số nguyên tố được tối ưu hóa:

import math

def is_prime_optimized(n):
if n <= 1:
return False # Không phải số nguyên tố

for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False # Không phải số nguyên tố

return True # Là số nguyên tố

Trong ví dụ này, chúng ta sử dụng hàm math.sqrt(n) để tính căn bậc hai của n và kiểm tra từ 2 đến căn bậc hai của n. Nếu không có số nào chia hết cho n trong khoảng này, thì n là số nguyên tố.

Kiểm tra số nguyên tố sử dụng thư viện sympy

Python cung cấp nhiều thư viện mạnh mẽ cho tính toán toán học và số học, và một trong những thư viện phổ biến để làm việc với số nguyên tố là sympy. sympy cho phép bạn kiểm tra số nguyên tố, tìm các số nguyên tố trong một khoảng, và thậm chí kiểm tra tính chất số nguyên tố của một số nguyên lớn.

Dưới đây là ví dụ về cách sử dụng thư viện sympy để kiểm tra số nguyên tố:

import sympy

def is_prime(n):
return sympy.isprime(n)

Một cách tương tự, chúng ta có thể gọi hàm này, sau đó nhập n kiểm tra n có phải số nguyên tố không không python như sau:

import sympy

def is_prime(n):
return sympy.isprime(n)

n = int(input(">> nhap so tu nhien: "))

if is_prime(n):
print(f"{n} la so nguyen to")
else:
print(f"{n} khong phai so nguyen to")

Sử dụng hàm kiểm tra số nguyên tố

Sau khi đã xác định cách kiểm tra số nguyên tố trong Python, chúng ta có thể sử dụng hàm này để kiểm tra số nguyên tố của một số bất kỳ, hoặc là tìm số nguyên tố trong khoảng chỉ định. Dưới đây là một số ví dụ:

Liệt kê tất cả các số nguyên tố nhỏ hơn n

Sử dụng phương pháp ở trên, chúng ta có thể liệt kê tất cả các số nguyên tố nhỏ hơn n bằng python.

Và dưới đây là ví dụ về chương trình liệt kê tất cả các số nguyên tố nhỏ hơn n trong python:

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

n = int(input(">> nhap mot so n: "))

for i in range(n):
if is_prime(i):
print(i, end =" ")

Kết quả:

>> nhap mot so n: 20
2 3 5 7 11 13 17 19

Tìm số nguyên tố trong khoảng a b

Chúng ta cũng có thể sử dụng một trong 2 phương pháp kiểm tra số nguyên tố ở trên để tìm số nguyên tố trong khoảng a b. Dưới đây là một ví dụ:

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

a = 2
b = 97

for i in range(a, b+1):
if is_prime(i):
print(i, end =" ")

Kết quả:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

Kiểm tra số nguyên to trong mảng python

Bằng cách kết hợp vòng lặp và kiểm tra từng phần tử có phải là số nguyên tố, chúng ta có thể kiểm tra số nguyên to trong mảng python như sau:

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

my_list= [1,2,6,8,10,13,17,20]

for i in my_list:
if is_prime(i):
print(i, end =" ")

Kết quả:

2 13 17

Tổng kết

Trên đây Kiyoshi đã hướng dẫn bạn cách kiểm tra số nguyên tố trong python rồi. Kiểm tra số nguyên tố là một vấn đề quan trọng trong lập trình, và Python cung cấp các công cụ đơn giản để thực hiện nó. Bài viết này đã giới thiệu cách kiểm tra số nguyên tố trong Python bằng cách sử dụng vòng lặp và tối ưu hóa kiểm tra bằng cách giới hạn vòng lặp đến căn bậc hai của số cần kiểm tra. Hi vọng rằng thông tin này sẽ giúp bạn hiểu cách làm việc với số nguyên tố trong Python và ứng dụng nó trong các dự án của bạn.

URL Link

https://laptrinhcanban.com/python/nhap-mon-lap-trinh-python/so-trong-python/kiem-tra-so-nguyen-to-trong-python/

Hãy chia sẻ và cùng lan tỏa kiến thức lập trình Nhật Bản tại Việt Nam!

HOME  › >>

Profile
きよしです!笑

Tác giả : Kiyoshi (Chis Thanh)

Kiyoshi là một cựu du học sinh tại Nhật Bản. Sau khi tốt nghiệp đại học Toyama năm 2017, Kiyoshi hiện đang làm BrSE tại Tokyo, Nhật Bản.