Số nguyên tố trong Python – Cách viết hàm kiểm tra

0
4743
so nguyen to python

Số nguyên tố trong ngôn ngữ Python là một dạng bài tập cơ bản nhất cho người mới học lập trình. Bài toán giúp bạn biết cách tạo một hàm, ứng dụng vòng for, câu điều kiện . . .

Số nguyên tố trong lập trình?

Trước tiên bạn cần phải hiểu số nguyên tố là gì?
Về mặt toán học, số nguyên tố là số chỉ có 2 ước là 1 và chính nó. Hay hiểu theo cách khác là nó chỉ chia hết cho 1 và chính nó.

Để viết được hàm kiểm tra số nguyên tố. Bạn cần phải áp dụng đúng tính chất toán học của nó, từ đó áp dụng vào thuật toán của mình. Sử dụng ngôn ngữ lập trình vận dụng linh hoạt các cấu trúc, cú pháp để hoàn thành được yêu cầu của bài toán.

Bài toán này dù dùng ngôn ngữ nào bạn cũng phải sử dụng đến cấu trúc vòng lặp, hoặc câu lệnh điều kiện. Cuối cùng là bạn phải kiểm tra xem số đó có chia hết cho số thứ 3 nào khác không.

Có một số tài liệu lập trình tiếng anh sẽ ghi số nguyên tố là: Prime number, bạn chú ý điều này nhé

so nguyen to trong python

Bài toán số nguyên tố trong Python

Yêu cầu bài toán: Bạn hãy viết hàm kiểm tra một số nguyên có phải là số nguyên tố hay không bằng ngôn ngữ lập trình Python.
In ra danh sách các số nguyên tố có trong dãy (list ).

Thuật toán

Bạn cần phải viết một hàm kiểm tra trả về giá trị True hoặc False. Cách làm tương tự như lọc số nguyên tố trong C++. Tham số cần truyền vào là một số nguyên N.

  • Nếu tham số truyền vào nhỏ hơn 2 thì trả về giá trị False.
  • Sử dụng một vòng lặp chạy tử 2 đến nhỏ hơn hoặc bằng N/2 hoặc cũng có thể chạy tới sqrt(N). Nếu tìm thấy giá trị mà N chia hết thì trả về False.
  • Ngược lại trả về True.
    (Không tìm thấy giá trị nào mà N chia hết ngoài 1 và chính nó)

Ngoài ra còn có một cách thứ 2 tối ưu hơn là sử dụng sàng số nguyên tố. Nhưng cách này hơi khó hiểu hơn một chút. Bạn có thể tham khảo nó tại đây!

Với thuật toán mình đưa ra, khuyến khích bạn tự viết ra code trước khi tham khảo cách làm của mình nhé!

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

Đọc qua thuật toán thì thấy có vẻ khó nhưng khi ứng dụng thì cực kì đơn giản. Tham khảo mã code của mình dưới đây nhé! Mình viêt bằng Python 3. Nếu bạn viết Python 2 thì không cần sửa gì nhiều vì Python 3 chỉ thêm các dấu ngoặc . . .

# Ham kiem tra so nguyen to trong python
def Songuyento(n):
    if(n<2):  # neu n nho hon 2 thi tra ve False
        return False
    i=2;
    while i <= n/2:
        if(n%i == 0): # neu n chia het cho bat ki so nao thi tra ve Fasle
            return False
        i+=1
    return True   # nguoc lai tra ve True

In ra số nguyên tố có trong danh sách

Áp dụng hàm trên, mình viết thành một chương trình nhỏ hoàn chính bằng ngôn ngữ Python. Mình chỉ thêm một số câu lệnh in ra màn hình. Lời gọi đến hàm kiểm tra.

Code Python 3 hoàn chỉnh:

# Bai toan in ra cac so Nguyen to bang Python

def Songuyento(n): #Ham kiem tra so nt
    if(n<2):
        return False
    i=2;
    while i <= n/2:
        if(n%i == 0):
            return False
        i+=1
    return True
a=[1,4,6,7,8,11,13]  # Khai bao mot list a
print('\n List A: ')
for i in a:
    print (i, end=" ")
print("\n")
print('{:-^30}'.format("KET QUA LOC SO NT"))
# Doan tren chi de in ra cho dep thoi ^^
for i in a:
    if(Songuyento(i)): # Goi toi ham kiem tra
        print(i, end= " ")

Kết quả chạy chương trình bên trên:

ham kiem tra so nguyen to trong python

Lời kết

Mong rằng qua bài chia sẻ của mình, bạn có thể phần nào hiểu được về cách sử dụng, cấu trúc cú pháp của ngôn ngữ Python. Coi đây như là một bài toán luyện tập để cải thiện khả năng lập trình của mình.
Chúc các bạn thành công!

Nếu bạn nào chưa cài môi trường Python cho máy tính thì tải về ở đâynhé!

LEAVE A REPLY

Please enter your comment!
Please enter your name here