Nếu n là hợp số thì dễ thấy n phải có ước số nguyên tố nhỏ hơn

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à số nguyên tố.

Giải sách bài tập Tin học 10 Bài 32: Ôn tập lập trình Python

Câu 32.9 trang 67 SBT 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à số nguyên tố.

Lời giải:

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[i])

* Chương trình chạy thử với 2 bộ dữ liệu là 12, 13.