Nội dung này trình bày 2 cách tìm số nguyên tố, thực chất là 1 nhưng khác ở điều kiện lặp giúp bài toán của chúng ta tìm được số nhanh hơn, tối ưu hơn. Còn cách tìm số nguyên tố bằng cách đặt cờ hiệu thì các bạn xem lại ở bài Kỹ thuật đặt lính canh, cờ hiệu

Cách thứ nhất:

# Tìm số nguyên tố:
# Số nguyên tố là số chỉ có 2 ước là 1 và chính nó.
# Suy ra, nếu 1 số có từ 3 ước trở lên thì số đó không phải số nguyên tố.
# Sử dụng vòng lặp để đếm số lượng số nguyên tố, tìm ra tổng số nguyên tố.
tong_uoc = 0
n = int(input("Nhập số n: "))
for i in range(2,n+1):
    # Nếu n chia hết cho i thì i chính là ước của n.
    # Nếu i là ước của n thì thực hiện tăng số lượng ước (đếm số lượng ước) lên 1.
    if n%i==0: tong_uoc=tong_uoc+1
# Nếu có 2 ước trở lên thì không phải là số nguyên tố.
if tong_uoc>=2: print(n,"không phải số nguyên tố")
# Nếu chỉ có 1 ước là chính nó thì là số nguyên tố vì khởi tại vòng lặp từ 2
# nên không cần kiểm tra số 1 là ước của n nữa. Vì số nào cũng chia hết cho 1.
# In ra n là số nguyên tố kho nó chỉ có duy nhất 1 ước.
else: print(n,"là số nguyên tố")

Cách thứ nhất: Tối ưu hơn vì dùng ít vòng lặp hơn.

Ta thấy rằng 1 số có ước số (trừ chính nó ra) nếu có 1 ước khác 1 sẽ nằm trong khoảng từ 2 đến căn bậc hai của nó. Nghĩa là nó 2 ước số ==> Không phải là số nguyên tố.

Ví dụ: + 15 có các ước là: 1,3,5. Ước thứ 2 của 15 là 3: 3 <

+ 20 có các ước là: 1,2,4,5,10. Ước thứ 2 của 20 là 2: 2 <

Vậy điều kiện lặp chỉ cần dừng ở

# Tìm số nguyên tố:
# Số nguyên tố là số chỉ có 2 ước là 1 và chính nó.
# Suy ra, nếu 1 số có từ 2 ước trở lên (khác 1) thì số đó không phải số nguyên tố.
# Nhưng thực chất thì số nào cũng chia hết cho 1 và chính nó.
# Nên có thể xét thấy số nguyên tố là số chỉ có 1 ước là 1 và không phải là số chẵn.
tong_uoc = 0
n = int(input("Nhập số n: "))
for i in range(1,(int(n**0.5))+1):
    # Nếu n chia hết cho i thì i chính là ước của n.
    # Nếu i là ước của n thì thực hiện tăng số lượng ước (đếm số lượng ước) lên 1.
    if n%i==0: tong_uoc=tong_uoc+1
# Nếu có 2 ước trở lên thì không phải là số nguyên tố.
if tong_uoc>=2: print(n,"không phải số nguyên tố")
# In ra n là số nguyên tố kho nó chỉ có duy nhất 1 ước.
else: print(n,"là số nguyên tố")