Nếu n là hợp số. Viết chương tì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 thì chỉ cần tìm trong các số 2, 3, ..., √n

Câu hỏi: 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 √n . Viết chương tì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 thì chỉ cần tìm trong các số 2, 3, ..., √n. 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:

def phanTichSoNguyen(n):

    i = 2

    A = []

while (n > 1):

         if (n % i == 0):

             n = n // i;

             A.append(i)

         else:

             i = i + 1

     return A

n = int(input("Nhập số nguyên dương n = "))

A = phanTichSoNguyen(n)

size = len(A)

if size == 1:

print("n là số nguyên tố")

else:

    print("n là hợp số")

sb = "";

    for i in range(0, size - 1):

         sb = sb + str(A[i]) + " x "

    sb = sb + str(A[size-1])

     print("Kết quả:", n, "=", sb)