32.9. 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 căn bậc hai của n. 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 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à số nguyên tố.
Bài Làm:
Chương trình có thể viết như sau:
from math import sqrt
n = int(input("Nhập số tự nhiên n: "))
m = n
k = 2
NT = [ ]
while m > 1:
while m%k != 0:
if k < sqrt(m):
k = k + 1
else:
k = m
NT.append(k)
m = m//k
count = len(NT)
if count == 0:
print(n, "không là số nguyên tố")
elif count == 1:
print(n,"là số nguyên tố")
else:
print(n, "là hợp số")
print(n,"=",end - " ")
for i in range(count):
if i < count - 1:
print(NT[i],"x",end = " ")
else:
print(NT[1])
