Kiểm tra số nguyên tố bằng Python

Hãy viết chương trình kiểm tra số nguyên tố bằng Python. Bạn chỉ cần viết chương trình ở mức cơ bản nhất trong Python và không cần phải tối ưu, bởi đã có bài viết thuật toán kiểm tra số nguyên tố khá chi tiết.

Bài giải

——————– ######## ——————–

Để giải bài này thì bạn phải hiểu chút khái niệm SNT đã nhé: Số nguyên tố là số nguyên lớn hơn 1 và chỉ chia hết cho 1 và chính nó.

Bài viết này được đăng tại

freetuts.net

, không được copy dưới mọi hình thức.

Dựa vào định nghĩa này ta rút ra được những tính chất sau: Số 2 là SNT chẵn duy nhất, bởi vì những số chẵn lớn hơn 2 luôn chia hết cho 1, 2 và chính nó.

Nếu một số thỏa 2 tính chất trên thì đó là số nguyên tố.

Dựa vào đây ta có thể phân tích toán như sau: Giả sử N là số cần kiểm tra.

Bài viết này được đăng tại [free tuts .net]

1. Kiểm tra nếu N bằng 2 thì là SNT => Break
2. Nếu N <= 1 thì không phải SNT => Break
3. Nếu N là số chẵn thì không phải SNT => Break
4. Lặp qua các số lẻ từ 2 -> (N – 1), nếu tồn tại số nào mà N chia hết thì không phải là SNT, nếu không thì đó là SNT.

Bài giải viết bằng ngôn ngữ Python như sau:

# HỌC PYTHON TẠI FREETUTS.NET
# TÁC GIẢ: CƯỜNG NGUYỄN

print("Chương trình đăng tại freetuts.net!")

print("Nhập vào số N lớn hơn 1: ")

# Lấy dữ liệu
n = int(input())
flag = True

# Kiểm tra SNT
if (n < 2):
    flag = False
elif (n == 2):
    flag = True
elif (n % 2 == 0):
    flag = False
else:
    # Lặp qua các số lẻ nên bắt đầu từ 3 với bước nhảy là 2
    for i in range(3, n, 2):
        if (n % i == 0):
            flag = False


# In kết quả
if flag == True:
    print(n, " là số nguyên tố")
else:
    print(n, " không phải là số nguyên tố")

Đây là kết quả khi mình nhập số nguyên tố 7 vào:

Danh sách bài tập Python cơ bản

Cùng chuyên mục: