Question

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 \(\sqrt{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 tố nhỏ nhất thì chỉ cần tìm trong các số 2, 3, …,\(\sqrt{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ố

Answer 1

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)