Nếu n là hợp số thì dễ thấy n phải có ước số nguyên tố nhỏ hơn hoặc bằng . Viết chương trình
167
19/06/2023
Vận dụng 3 trang 155 Tin học 10: Nếu n là hợp số thì dễ thấy n phải có ước số nguyên tố nhỏ hơn hoặc bằng . Viết chương trình tối ưu hoá hơn nhiệm vụ 1, bài 31, theo cách sau: để tìm ước số nguyên tố nhỏ nhất chỉ cần tìm trong các số 2, 3, …, . Nếu trong dãy trên không tìm thấy ước của n thì kết luận ngay n là nguyên tố.
Trả lời
import math
print("Nhập vào số n lớn hơn 1: ")
# Lấy dữ liệu
n = int(input())
flag = True
#Su dung cau truc re nhanh xu ly truong hop n <= 0
if (n < 2):
flag = False
elif (n == 2):
flag = True
elif (n % 2 == 0):
flag = False
else:
#Su dung vong lap for de duyet cac so tu 2 den can bac hai cua n
for i in range(2, int(math.sqrt(n))+1):
#Kiem tra tinh chia het
if n % i == 0:
flag == False
break
else:
flag == True
# 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ố")
Hình 1. Chương trình
Hình 2. Kết quả chạy thử