Tìm các số nguyên tố viết dưới dạng tổng hai số chính phương với Python

10
Lập trình 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. Nhập số n, kiểm tra xem n có là số nguyên tố hay không? Nếu thỏa mãn ghi ra hai số chính phương có tổng bằng n. Ngược lại, ghi ra -1. Ví dụ: 

BDNT.INP

BDNT.OUT

61

25 36

Code tham khảo:

import math
def nguyenTo(n):
    if n < 2: return False
    else:
        m = math.sqrt(n)
        i = 2
        while (n % i) and (i < m):
            i = i + 1
        if i > m: return True
        else: return False
def cp(n):
    if math.sqrt(n)==int(math.sqrt(n)):
        return True
    else:
        return False
fin = open("BDNT.INP","r")
fout = open("BDNT.OUT","w")
m = fin.readline()
n = int(m)
if nguyenTo(n):
    if n % 4 == 1 or n == 2:
        a = 1
        while not(cp(a)) or not(cp(n-a)):
            a = a + 1
        fout.write(str(a) + " " + str(n - a))
    else: fout.write(str("-1"))
else: fout.write(str("-1"))
fin.close
fout.close