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