Biểu diễn dạng tổng 2 số chính phương trong Python

Bài toán: “Những số nguyên tố khi chia cho 4 dư 1 thì luôn biểu diễn được dưới dạng tổng của 2 số chính phương”. Kiểm tra N có nguyên tố hay không? Nếu N nguyên tố, kiểm tra xem có thể phân tích N thành tổng của hai số chính phương a và b hay không? Nếu được hãy tìm a và b.

Để kiểm tra xem một số N có phải là số nguyên tố hay không, bạn có thể sử dụng các thuật toán kiểm tra số nguyên tố như sàng Eratosthenes hoặc kiểm tra liệu N có chia hết cho các số nguyên tố nhỏ hơn nó không.

Nếu N được xác định là một số nguyên tố, chúng ta có thể kiểm tra xem liệu N có thể phân tích thành tổng của hai số chính phương a và b không. Để làm điều này, chúng ta có thể thực hiện các bước sau đây:

1. Kiểm tra các số chính phương nhỏ hơn hoặc bằng N để xác định các số chính phương có thể là a và b. Số chính phương là số mà căn bậc hai của nó là một số nguyên. Ví dụ: 1, 4, 9, 16, …
2. Với mỗi số chính phương a, kiểm tra xem N – a có phải là số chính phương hay không. Nếu là số chính phương, ta đã tìm được hai số chính phương a và b sao cho N = a + b.

Dưới đây là một đoạn mã Python minh họa để kiểm tra điều này:

import math

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def find_square_sums(n):
    if not is_prime(n):
        return "N không phải là số nguyên tố."
    
    for a in range(1, int(math.sqrt(n)) + 1):
        b = n - a
        if math.isqrt(b)**2 == b:
            return f"{n} = {a}^2 + {b}^2"
    
    return "Không tìm thấy phân tích của N thành tổng của hai số chính phương."

# Ví dụ sử dụng:
N = 17
print(find_square_sums(N))

Kết quả sẽ là “17 = 1^2 + 16^2”, vì 17 là số nguyên tố và có thể phân tích thành tổng của hai số chính phương là 1 và 16.